A simplicial complex is said to be flag if it is the clique complex of its underlying graph. In other words, one starts with the graph and add all simplices of all dimensions that are compatible with this -skeleton. A subcomplex of a flag complex is said to be induced if it is flag, and if whenever vertices and is an edge of , we also have that is an edge of .
Does there exist a flag simplicial complex with countably many vertices, such that the following extension property holds?
[Extension property] For every finite or countably infinite flag simplicial complex and vertex , and for every embedding of as an induced subcomplex , can be extended to an embedding of as an induced subcomplex.
It turns out that such a does exist, and it is unique up to isomorphism (both combinatorially and topologically). Other interesting properties of immediately follow.
- contains homoemorphic copies of every finite and countably infinite simplicial complex as induced subcomplexes.
- The link of every face is homeomorphic to itself.
- The automorphism group of acts transitively on -dimensional faces for every .
- Deleting any finite number of vertices or edges of and the accompanying faces does not change its homeomorphism type.
Here is an easy way to describe . Take countably many vertices, say labeled by the positive integers. Choose a probability such that , and for each pair of integers , connect to by an edge with probability . Do this independently for every edge.
This is sometimes called the Rado graph, and because it is unique up to isomorphism (and in particular because it does not depend on ) it is sometimes also called the random graph. It is also possible to construct the Rado graph purely combinatorially, without resorting to probability. The I have in mind is of course just the clique complex of the Rado graph.
We can filter the complex by setting to be the induced subcomplex on all vertices with labels , and this allows us to ask more refined questions. (Now the choice of affects the asymptotics, so we assume .) From the perspective of homotopy theory, is not a particularly interesting complex; it is contractible. (This is an exercise, one should check this if it is not obvious!) However, has interesting topology.
As , the probability that is contractible is going to . It was recently shown that has asymptotically almost surely (a.a.s.) at least nontrivial homology groups, concentrated around dimension . For comparison, the dimension of is .
I think one can probably show using the techniques from this paper that there is a.a.s. no nontrivial homology above dimension or below dimension . It is still not clear (at least to me) what happens between dimensions and . It seems that a naive Morse theory argument can give that the expected dimension of homology is small in this range, but to show that it is zero would take a more refined Morse function. Perhaps a good topic for another post would be “Morse theory in probability.”
Another question: given a non-contractible induced subcomplex (say an embedded -dimensional sphere) on a set of vertices, how many vertices should one expect to add to before becomes contractible in the larger induced subcomplex? For example, it seems that once you have added about vertices, it is reasonably likely that one of these vertices induces a cone over , but is it possible that the subcomplex becomes contractible with far fewer vertices added?