Universal countable uniform hypergraph

ID: universal-countable-uniform-hypergraph

The universal countable uniform hypergraph is the unique, up to hypergraph isomorphism, countably infinite -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 -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 -uniform hypergraph as an induced subhypergraph, explaining the word universal. Its isomorphism type is independent of .

New to topics? Read the docs here!