Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2010/iii/paper-12/1/i/solution
Past exam of the mathematics course of the University of Cambridge 2010 iii Paper 12 1 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
The edge choices are understood to be independent, and 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 , prescribe a family . We want a new vertex such thatFor any , 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 . The successes are therefore independent random variables with the same positive probability . The probability that the first candidates all fail is . 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 , 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 and be two countably infinite -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 of . Its incident hyperedges with each -subset of the current domain specify a pattern on the matched vertices of . The hypergraph extension property supplies an unused vertex of with exactly this pattern. Adding preserves and reflects every hyperedge in the enlarged domain. At the next step, take the least unused vertex of and perform the identical construction with and 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 -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 . ThereforeThe hypergraph isomorphism type does not depend on . In the case it is the Rado graph. For , the argument says that the infinitely many selected and unselected singleton vertices determine the same one-uniform structure for every .
New to topics? Read the docs here!