Hypergraph extension property

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.

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)$.

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.