Topological Turán theory

I just came across the following interesting question of Nati Linial.

If a two-dimensional simplicial complex has vertices and faces, does it necessarily contain an embedded torus?

I want to advertise this question to a wider audience, so I’ll explain first why I think it is interesting.

First of all this question makes sense in the context of Turán theory, a branch of extremal combinatorics. The classical Turán theorem gives that if a graph on vertices has more than edges then it necessarily contains a complete subgraph on vertices. This is tight for every and .

One could ask instead how many edges one must have before there is forced to be a cycle subgraph, where it doesn’t matter what the length of the cycle is. This is actually an easier question, and it is easy to see out that if one has edges there must be a cycle.
It also seems more natural, in that it can be phrased topologically: how many edges must be added to vertices before we are forced to contain an embedded image of the circle?

What is the right two-dimensional analogue of this statement? In particular, is there a constant such that a two-dimensional simplicial complex with vertices and at least two-dimensional faces must contain an embedded sphere ? If so, then this is essentially best possible. By taking a cone over a complete graph on vertices, one constructs a two-complex on vertices with faces and no embedded spheres. Without having thought about it at all, I am not sure how to do better.

In any case, the corresponding question for torus seems more interesting, but for different reasons. In a paper with Eric Babson and Chris Hoffman we looked at the fundamental group of random two-complexes, as defined by Linial and Meshulam, and found the rough threshold for vanishing of the fundamental group. To show that the fundamental group was nontrivial when the number of faces was small required a lot of work — in particular, in order to apply Gromov’s local-to-global method for hyperbolicity, we needed to prove that the space was locally negatively curved, and this meant classifying the homotopy type of subcomplexes up to a large but constant size.

It turned out that the small subcomplexes were all homotopy equivalent to wedges of circles, spheres, and projective planes. In particular, we show that there are not any torus subcomplexes, at least not of bounded size. (Linial may have recently shown that there are not embedded tori, even of size tending to infinity with .) On the other hand, just on the other side of the threshold embedded tori abound in great quantity. It is interesting that something similar happens in the density random groups of Gromov — that the threshold for vanishing of the density random group corresponds to the presence of tori subcomplex in the naturally associated two-complex. It is not clear to me if this is a general phenomenon, coming geometrically from the fact that a torus admits a flat metric.

Some of the great successes of the probabilistic method in combinatorics have been in existence proofs when constructions are hard or impossible to come by. It would be nice to have interesting or extremal topological examples produced this way. Nati’s question suggests an interesting family of extremal problems in topological combinatorics, and it might make sense that in certain cases, random simplicial complexes have nearly maximally many faces for avoiding a particular embedded subspace.

Update: Nati pointed me to the paper Sós, V. T.; Erdos, P.; Brown, W. G., On the existence of triangulated spheres in $3$-graphs, and related problems. Period. Math. Hungar. 3 (1973), no. 3-4, 221–228.
Here it is shown that is the right answer for the sphere. Their lower bound is constructive, based on projective planes over finite fields. Nati said that being initially unaware of this paper, he found a probabilistic proof that works just as well as a lower bound for every fixed 2-manifold. So it seems that the main problem here is to find a matching upper bound for the torus.