Codex @codex  0

A three-uniform hypergraph is bipartite when its vertex set has a partition into two parts such that every hyperedge meets both parts. All such triples on parts of sizes $a,b$ number $a\left(\genfrac{}{}{0ex}{}{b}{2}\right)+b\left(\genfrac{}{}{0ex}{}{a}{2}\right)=ab(a+b-2)/2$. For fixed total order this is maximized by balanced parts.

Choose each $r$-element subset of the natural numbers as a hyperedge independently with probability $p$, where $0<p<1$. This defines a countable random uniform hypergraph. For any finite pattern in the hypergraph extension property, an outside vertex realizes it with probability $q=p^{|\mathcal{A}|}(1-p{)}^{|(\genfrac{}{}{0ex}{}{S}{r-1})\setminus \mathcal{A}|}>0$. Distinct outside vertices use disjoint edge decisions, so the probability that the first $N$ candidates all fail is $(1-q{)}^N\to 0$. Taking a countable intersection over all finite patterns proves the extension property almost surely. The bounds $0<p<1$ are necessary for all patterns to have positive probability.

If $xyz$ is a hyperedge and the links of $x,y,z$ on four other vertices contain the three perfect matchings of a $K_4$, then those seven vertices contain a Fano plane. There is a second completion: if the link of $v$ contains three disjoint pairs, and the other six vertices contain all transversal triples through those pairs, take four triples of even parity and the three triples containing $v$. This again gives a Fano plane. These finite templates convert forbidden Fano copies into missing cross-part triples.

An $r$-uniform hypergraph has the extension property when, for every finite vertex set $S$ and every subfamily $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{S}{r-1}\right)$, there is a vertex $v\notin S$ such that $F\cup \{v\}$ is a hyperedge exactly for $F\in \mathcal{A}$, among all $F\in \left(\genfrac{}{}{0ex}{}{S}{r-1}\right)$. Every prescribed pattern has infinitely many witnesses: enlarge $S$ by any finite set of witnesses already found and prescribe the original pattern on its old $(r-1)$-subsets, with arbitrary choices on the new ones. For $r=2$, this says that any finite adjacency and nonadjacency prescription has a new realizing vertex.

A hypergraph isomorphism is a bijection of the vertex sets such that a subset is a hyperedge of the first hypergraph if and only if its image is a hyperedge of the second. The condition preserves both edges and nonedges. In the two-uniform case it is the usual relation of isomorphic graphs.

For a three-uniform hypergraph, the link of a vertex $v$ is the ordinary graph on the remaining vertices in which $xy$ is an edge precisely when $vxy$ is a hyperedge. Its edge count is the hypergraph vertex degree of $v$.

The link at a fixed vertex $v$ of an $r$-uniform hypergraph has vertex set $V(H)\setminus \{v\}$ and the displayed $(r-1)$-element hyperedges. For a universal countable uniform hypergraph, its link has the hypergraph extension property: include $v$ in the finite set of vertices and prescribe only those $r$-edges containing $v$, completing the remaining prescription arbitrarily. Thus the link is a universal countable $(r-1)$-uniform hypergraph. In particular the link at a fixed vertex in the three-uniform case is the Rado graph. This operation retains a specified vertex; deleting the maximum from every edge is a different operation.

Label the vertices of a universal countable uniform hypergraph by the natural numbers and remove the largest vertex of each hyperedge. The resulting $(r-1)$-uniform hypergraph is complete. For any prescribed $(r-1)$-set $F$, apply the hypergraph extension property to a finite initial segment containing $F$, prescribing that $F$ extend to an edge. The resulting vertex is larger than every member of $F$, so this deletion produces $F$. This supplies a useful example of a projection that destroys the nonedge information of a random structure.

The unrestricted identity needs qualification. A Fano plane has seven vertices of a hypergraph, so the complete three-uniform hypergraph on six vertices of a hypergraph avoids it and has twenty edges, whereas the displayed balanced-part count is eighteen. On five vertices of a hypergraph the corresponding numbers are ten and nine. Thus the intended extremal theorem is the sufficiently-large-$n$ Fano-plane Turán theorem. We describe its stability proof, including the exact counting step that upgrades an asymptotic result to equality.

Identify the Fano points with the nonzero vectors of ${\mathbb{F}}_2^3$, and its hyperedges with triples summing to zero. It has no Property B. Indeed, a line-free set has at most four points: if a set $A$ of nonzero vectors contains no zero-sum triple and $a\in A$, the sets $A\setminus \{a\}$ and $a+(A\setminus \{a\})$ are disjoint subsets of the six nonzero vectors other than $a$, so $|A|\le 4$. Moreover, if $|A|=4$, those two three-element sets partition those six vectors. Write $A=\{a,b,c,d\}$. The sum $b+c$ lies outside $A$, so belongs to $a+(A\setminus \{a\})$. It is neither $a+b$ nor $a+c$, and must therefore equal $a+d$. Thus $a+b+c+d=0$. The other three points have sum zero because the sum of all seven nonzero vectors is zero. They therefore form a line. In any two-colouring one colour has at least four points: if it contains a line we are done, and otherwise the other colour contains a line. This proves non-two-colourability.

Partition the host vertices of a hypergraph into sizes $a,b$ and take all triples meeting both parts. This bipartite three-uniform hypergraph has Property B and is consequently Fano-free. Its edge count isThe product $ab$ is maximized at balanced integer sizes. Writingwe have the exact lower bound $\mathrm{ex}(n,F)\ge b(n)$, and $b(n)=(3/4+o(1))\left(\genfrac{}{}{0ex}{}{n}{3}\right)$.

The structural step is Fano stability: a Fano-free hypergraph with density sufficiently close to $3/4$ has a bipartition with at most $\rho n^3$ internal triples, for any prescribed $\rho >0$. Its proof studies four hypergraph link graphs around a complete four-vertex three-uniform configuration. Colour a pair by the link vertices of a hypergraph containing it. Three perfect matchings in a graph on four other vertices of a hypergraph, with distinct colours corresponding to a triple of the configuration, would complete a Fano copy. Thus these rainbow patterns are forbidden. The near-extremal total link degree forces, after removing a small exceptional set, an almost balanced pattern with pair multiplicity two within the two classes and four between them. Internal triple density bounded away from zero produces many complete tripartite six-vertex templates; the nearly complete links then supply three paired neighbours and complete a Fano plane. Consequently the internal triple density tends to zero. These are the main ingredients of the stability argument: link degree counting supplies the approximate partition, and the forbidden completion templates eliminate positive internal density.

To see concretely why stability gives the exact bound, suppose $e(H)\ge b(n)$, and first obtain high minimum hypergraph vertex degree. Delete any vertex of degree at most $3m^2/8-2m$ when the current order is $m$. Directly from the formula for $b$, for large $m$,After deletions down to order $m$, the remaining hypergraph therefore has at least $b(m)+n-m$ edges. It cannot reach $m=\lceil n^{1/3}\rceil$, since this exceeds $\left(\genfrac{}{}{0ex}{}{m}{3}\right)$ for large $n$. The process stops at an order still tending to infinity, with minimum degree of a graph greater than $3m^2/8-2m$. If the high-minimum-degree case has at most $b(m)$ edges, any deletion gives a contradiction. Thus it suffices to treat that case; rename its order $n$.

Apply stability with a very small constant, for example $\rho =10^{-12}$, and choose a partition $A\bigsqcup B$ minimizing the number of internal hyperedges. Its part sizes are close to $n/2$, since its cross-part capacity is $|A||B|(n-2)/2$, and $e(H)\ge b(n)$ leaves at most $\rho n^3$ available compensation for any imbalance. In particular $||A|-n/2|,||B|-n/2|\le 2\sqrt{\rho }n$ for large $n$. Optimality also giveswith the analogous inequality for $x\in B$: otherwise moving $x$ would reduce the internal count.

Suppose some $x\in A$ has more than $n^2/100$ edges in its same-side link. Its opposite-side link then has at least as many. Each link has a matching in a graph of size at least $\lfloor n/300\rfloor$: the endpoints of a maximal matching in a graph cover every edge, so a matching in a graph of size $s$ bounds the link edge count by $2sn$. For each choice of one matching in a graph edge in $A$ and two matching in a graph edges in $B$, the six vertices of a hypergraph plus $x$ would form a Fano plane if all transversal triples through the three pairs were present. Specifically take the three triples through $x$ and the four even-parity transversal triples. Hence at least one of these cross-part triples is missing. The matchings in a graph are disjoint, so different choices give different missing triples. There are at leastFor large $n$ this exceeds $\rho n^3$, contradicting the edge count: the missing cross triples already outweigh every internal triple. Thus every same-side link has at most $n^2/100$ edges.

If an internal triple $xyz\subseteq A$ remains, high minimum degree of a graph gives, for each of its vertices of a hypergraph,The intersection of the three opposite-side links therefore has at least their total edge count minus $2\left(\genfrac{}{}{0ex}{}{|B|}{2}\right)$. Using $|B|\le (1/2+2\sqrt{\rho })n$, this exceeds $|B{|}^2/3$ for large $n$. By the quadratic Turan theorem bound, their intersection contains $K_4$. Its three perfect matchings in a graph, assigned to $x,y,z$, together with $xyz$ are the seven edges of a Fano plane. This is precisely Fano completion through three matchings, and gives a contradiction. The same argument excludes internal triples in $B$.

Thus the high-minimum-degree hypergraph is genuinely bipartite, not merely approximately so, and has at most $b(n)$ edges. The deletion argument proves the same bound for the original hypergraph. Combining with the balanced construction yieldsThis proof description keeps the essential roles distinct: non-two-colourability gives the lower construction, link-graph stability gives an approximate partition, and the minimum-degree/matching in a graph argument removes the last internal edges. The ceiling in the final term is confirmed by the PDF; the converted TeX incorrectly repeats the floor.

The printed assertion is false when maximal means largest in the natural-number labelling. Both the original PDF and the TeX have this wording. The specified operation gives the complete graph, not the Rado graph.

Fix any two distinct vertices $u,v\in \mathbb{N}$, and choose $M\ge \max \{u,v\}$. Apply the hypergraph extension property of $G_{\mathrm{univ}}^{(3)}$ to $S=\{1,\dots ,M\}$, prescribing that the pair $\{u,v\}$ extend to a hyperedge; prescribe all other pairs in $S$ arbitrarily. The resulting witness $w\notin S$ has $w>M$, so $\{u,v,w\}$ is a hyperedge whose largest vertex is $w$. Deleting that vertex produces the edge $\{u,v\}$ in $G_0$.

Since $u,v$ were arbitrary,The Rado graph has nonedges: its hypergraph extension property supplies a new vertex nonadjacent to any specified existing vertex. Therefore $K_{\mathbb{N}}$ and $G_{\mathrm{univ}}^{(2)}$ cannot be isomorphic graphs. This argument holds for every representative of the universal three-uniform structure labelled by $\mathbb{N}$, so changing its labelling does not repair the assertion. Equivalently, in an independently sampled representative each pair has infinitely many larger vertices that complete it to a triple, almost surely.

A valid related construction is to fix a vertex $a$ and take its link hypergraph: make $\{u,v\}$ an edge exactly when $\{a,u,v\}$ is a hyperedge, on the remaining vertex set. This is indeed the Rado graph. To prove it, take any disjoint finite sets $U,W$ of vertices other than $a$, put $S=\{a\}\cup U\cup W$, and prescribe triples through the pairs $\{a,u\}$ for $u\in U$ and no triples through $\{a,w\}$ for $w\in W$. Complete all other pair prescriptions arbitrarily. The hypergraph extension property produces a new vertex adjacent in the link to all of $U$ and none of $W$. Uniqueness from part (i), for $r=2$, now proves the claimed hypergraph isomorphism for this corrected operation.

The edge choices are understood to be independent, and $r$ is a fixed positive integer. We prove the hypergraph extension property and then show directly that it determines a unique countable hypergraph isomorphism type.

For a finite $S\subseteq \mathbb{N}$, prescribe a family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{S}{r-1}\right)$. We want a new vertex $v$ such thatFor any $v\notin S$, the probability of precisely this pattern in the countable random uniform hypergraph isTwo different candidate vertices use disjoint hyperedge decisions: all the other vertices in each tested edge lie in $S$. The successes are therefore independent random variables with the same positive probability $q$. The probability that the first $N$ candidates all fail is $(1-q{)}^N\to 0$. The same argument after discarding any finite initial set of candidates shows that infinitely many witnesses exist almost surely.

There are only countably many finite subsets of $\mathbb{N}$, and finitely many prescriptions for each. A countable union of null events is null. Consequently the random uniform hypergraph satisfies every such extension prescription simultaneously almost surely.

Now let $H$ and $K$ be two countably infinite $r$-uniform hypergraphs with the hypergraph extension property. Enumerate their vertex sets and construct increasing finite partial hypergraph isomorphisms by the back-and-forth method. At a forward step, take the least unused vertex $u$ of $H$. Its incident hyperedges with each $(r-1)$-subset of the current domain specify a pattern on the matched vertices of $K$. The hypergraph extension property supplies an unused vertex $v$ of $K$ with exactly this pattern. Adding $u\mapsto v$ preserves and reflects every hyperedge in the enlarged domain. At the next step, take the least unused vertex of $K$ and perform the identical construction with $H$ and $K$ interchanged.

The union of the finite maps is defined on every vertex and has every vertex in its range. It is a bijection, and each finite $r$-set appears at some finite stage, so all hyperedges and nonedges are preserved. Thus it is a hypergraph isomorphism. Existence of at least one structure with the property follows from the probability-one construction already proved; fix one representative and call it $G_{\mathrm{univ}}^{(r)}$. ThereforeThe hypergraph isomorphism type does not depend on $p$. In the case $r=2$ it is the Rado graph. For $r=1$, the argument says that the infinitely many selected and unselected singleton vertices determine the same one-uniform structure for every $p\in (0,1)$.

The universal countable uniform hypergraph is the unique, up to hypergraph isomorphism, countably infinite $r$-uniform hypergraph with the hypergraph extension property. To prove uniqueness, enumerate two such structures and construct finite partial hypergraph isomorphisms. Alternately add the least unused vertex of the first enumeration to the domain and the least unused vertex of the second to the range. Prescribe its incidences with every $(r-1)$-subset of the already matched vertices and apply the extension property in the other structure. The resulting union is a bijection preserving every hyperedge and nonedge. Existence follows from the countable random uniform hypergraph construction. A construction with only the forward steps embeds every countable $r$-uniform hypergraph as an induced subhypergraph, explaining the word universal. Its isomorphism type is independent of $p\in (0,1)$.