Topological Turán theory

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

If a two-dimensional simplicial complex has n vertices and \Omega(n^{5/2}) 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 n vertices has more than \displaystyle{ \left( 1-\frac{1}{r} \right) \frac{n^2}{2} } edges then it necessarily contains a complete subgraph K_r on r vertices. This is tight for every r and n.

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 n 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 n 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 C such that a two-dimensional simplicial complex with n vertices and at least C n^2 two-dimensional faces must contain an embedded sphere S^2? If so, then this is essentially best possible. By taking a cone over a complete graph on n-1 vertices, one constructs a two-complex on n vertices with {n -1 \choose 2} 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 n.) 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 n^{5/2} 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.


A young person’s guide to the Hopf fibration

I enjoyed this recent arXiv post by Zack Treisman, apparently notes for a summer course for high school students he taught. It leads a beginning mathematician by discovery through the basics of arithmetic of complex numbers, higher dimensional geometry, a word or two on knot theory, and then onto the main topic: the Hopf fibration. I wish someone had told me about these things when I was in high school.

Thanks to several beautiful illustrations by Lun-Yi Tsai and Zack’s charming writing style, it is fun to flip through for mathematicians who are already familiar with these ideas as well. I hope Zack and Lun-Yi make a coffee table book one day.


The Rado complex

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 1-skeleton. A subcomplex F' of a flag complex F is said to be induced if it is flag, and if whenever vertices x, y \in  F' and \{ x,y \} is an edge of F, we also have that \{ x,y \} is an edge of F'.

Does there exist a flag simplicial complex \Delta with countably many vertices, such that the following extension property holds?

[Extension property] For every finite or countably infinite flag simplicial complex X and vertex v \in X, and for every embedding of X-v as an induced subcomplex i: X -v \hookrightarrow \Delta , i can be extended to an embedding \widetilde{i}: X \hookrightarrow \Delta of X as an induced subcomplex.

It turns out that such a \Delta does exist, and it is unique up to isomorphism (both combinatorially and topologically). Other interesting properties of \Delta immediately follow.

\Delta contains homoemorphic copies of every finite and countably infinite simplicial complex as induced subcomplexes.

– The link of every face \sigma \in \Delta is homeomorphic to \Delta itself.

– The automorphism group of \Delta acts transitively on d-dimensional faces for every d.

– Deleting any finite number of vertices or edges of \Delta and the accompanying faces does not change its homeomorphism type.

Here is an easy way to describe \Delta. Take countably many vertices, say labeled by the positive integers. Choose a probability p such that 0 < p < 1, and for each pair of integers \{ m,n \}, connect m to n by an edge with probability p. 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 p) it is sometimes also called the random graph. It is also possible to construct the Rado graph purely combinatorially, without resorting to probability. The \Delta I have in mind is of course just the clique complex of the Rado graph.

We can filter the complex \Delta by setting \Delta(n) to be the induced subcomplex on all vertices with labels \le n, and this allows us to ask more refined questions. (Now the choice of p affects the asymptotics, so we assume p = 1/2.) From the perspective of homotopy theory, \Delta is not a particularly interesting complex; it is contractible. (This is an exercise, one should check this if it is not obvious!) However, \Delta(n) has interesting topology.

As n \to \infty, the probability that \Delta(n) is contractible is going to 0. It was recently shown that \Delta(n) has asymptotically almost surely (a.a.s.) at least \Omega( \log{ \log{ n}} ) nontrivial homology groups, concentrated around dimension \log_2{n}. For comparison, the dimension of \Delta(n) is d \approx 2 \log_2{n}.

I think one can probably show using the techniques from this paper that there is a.a.s. no nontrivial homology above dimension d/2 or below dimension d/4. It is still not clear (at least to me) what happens between dimensions d/4 and d/2. 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 d-dimensional sphere) \Delta' \subset \Delta on a set S of k vertices, how many vertices f(k) should one expect to add to S before \Delta' becomes contractible in the larger induced subcomplex? For example, it seems that once you have added about 2^k vertices, it is reasonably likely that one of these vertices induces a cone over \Delta', but is it possible that the subcomplex becomes contractible with far fewer vertices added?

An application of disc packing to statistical mechanics

I recently posted an article to the arXiv, on a problem suggested by Persi Diaconis. “Hard discs in a box” is a classical setting in statistical physics. One very simple model of matter is as n non-overlapping (or hard) discs of radius r, bouncing around inside a unit square. This is a very well studied model in computational statistical physics, although not much seems to be known so far mathematically. In particular, the statistical physicists observe experimentally that there is a phase transition of some kind when \pi r^2 n  \approx 0.70.

The details of what exactly it means that there is a phase transition will have to be left for another post. But what is relevant for us here is how they sample a uniformly random configuration of hard discs, via the Metropolis algorithm. (Please see the recent survey article by Persi Diaconis in the Bulletin of the AMS.) Basically, one starts with the discs in a reasonable starting configuration, say evenly spaced along some lattice, and then one applies Metropolis, which means the following. Choose one of the n discs uniformly randomly, and make a small perturbation of its position. If this results in overlapping discs, or going out of the square, reject the move, otherwise accept it.

Under certain hypotheses on your space, one can show that this Markov chain converges to the uniform distribution on the space of all possible configurations. But to know this, one must know that the Markov chain is irreducible, and in particular that the configuration space is path connected.

Diaconis, Lebeau, and Michel observed that there is some constant c_1 such that if r \le  c_1 / n, the discs can always be freely rearranged, and in particular that the Metropolis Markov chain is irreducible. The real point of their article was to put useful upper bounds on the mixing time of Metropolis in general, and then they applied it to the hard discs setting as a motivating example. It would be nice if the same holds even in the range of the phase transition; in other words we would like to replace n in the above statement with \sqrt{n}.

However, their result is essentially best possible. In my recent preprint, I gave examples of stable configurations (meaning that no single disc can move) with r > c_2 / n. Here is a picture that should give some feeling for the main idea behind the construction.

A stable configuration of discs

There is still quite a lot to do here. As Persi points out in his survey article, these configuration spaces of hard discs are naturally endowed with a topological structure, as well as probability measure. In his survey article, he says, “very, very little is known about the topology of these spaces.”

At a workshop on, “Topological complexity of random sets,” this past week at the American Institute of Mathematics, Yuliy Baryshnikov, Peter Bubenik, and I were able to establish a connection to classical algebraic topology. In particular, if r < \frac{1}{2 n}, then the configuration space C(n; r) is not only path connected, but it is homotopy equivalent to the classical configuration space of n labeled points in the plane. It is fairly clear that this happens for some sufficiently small radius, but as far as we know, no one had put any quantitative bounds on it yet.

In another article, in preparation, I discuss the combinatorial aspects of these configuration spaces, and give an example of what I call a “transitionary” configuration, as a first attempt to give a heuristic explanation of the phase transition near \pi r^2 n =0.70. The disc packing example illustrated above might be more interesting to discrete geometers than to probabilists, since one would like to believe that examples like this are rather rare, in a measure theoretic sense. Nevertheless, we believe that deeply understanding the various geometric and topological features of these spaces, and how they change as r varies, might be a first step in explaining the phase transition mathematically.

V-Cube 7

This looks neat:

7 x7 x 7 Rubik’s Cube. Will report back with a review after it comes in the mail…

I haven’t bothered to check their claim of a ludicrously large number of possible positions (1.95 \times 10^{160}) yet. But I remember the packaging on the original Rubik’s Cubes advertising something like, “millions and millions of positions possible,” which is true, and might be (quantitatively speaking) one of the biggest understatements in human history. I think the right answer for the 3 \times 3 \times 3 is roughly 4 \times 10^{19}? I remember some people telling me that it was actually physically impossible to build bigger than 5 \times 5 \times 5, but I guess surprisingly it’s not.

What I’d really like to see is a nice physical implementation of the four-dimensional  cube.

Update: Got the V-Cube 5, 6, and 7 in the mail, and they are great. Very cleverly made, they turn well and make a satisfying “click” when aligned. A piece might pop out if you turn it funny, but it clicks back in pretty easily.