A conjecture concerning random cubical complexes

Nati Linial and Roy Meshulam defined a certain kind of random two-dimensional simplicial complex, and found the threshold for vanishing of homology. Their theorem is in some sense a perfect homological analogue of the classical Erdős–Rényi characterization of the threshold for connectivity of the random graph.

Linial and Meshulam’s definition was as follows. $Y(n,p)$ is a complete graph on $n$ vertices, with each of the ${n \choose 3}$ triangular faces inserted independently with probability $p$ , which may depend on $n$ . We say that $Y(n,p)$ almost always surely (a.a.s) has property $\mathcal{P}$ if the probability that $Y(n,p) \in \mathcal{P}$ tends to one as $n \to \infty$ .

Nati Linial and Roy Meshulam showed that if $\omega$ is any function that tends to infinity with $n$ and if $p = (\log{n} + \omega) / n$ then a.a.s $H_1( Y(n,p) , \mathbb{Z} / 2) =0$ , and if $p = (\log{n} - \omega) / n$ then a.a.s $H_1( Y(n,p) , \mathbb{Z} / 2) \neq 0$ .

(This result was later extended to arbitrary finite field coefficients and arbitrary dimension by Meshulam and Wallach. It may also be worth noting for the topologically inclined reader that their argument is actually a cohomological one, but in this setting universal coefficients gives us that homology and cohomology are isomorphic vector spaces.)

Eric Babson, Chris Hoffman, and I found the threshold for vanishing of the fundamental group $\pi_1(Y(n,p))$ to be quite different. In particular, we showed that if $\epsilon > 0$ is any constant and $p \le n^{-1/2 -\epsilon}$ then a.a.s. $\pi_1 ( Y(n,p) ) \neq 0$ and if $p \ge n^{ -1/2 + \epsilon}$ then a.a.s. $\pi_1 ( Y(n,p) ) = 0$ . The harder direction is to show that on the left side of the threshold that the fundamental group is nontrivial, and this uses Gromov’s ideas of negative curvature. In particular to show that the $\pi_1$ is nontrivial we have to show first that it is a hyperbolic group.

[I want to advertise one of my favorite open problems in this area: as far as I know, nothing is known about the threshold for $H_1( Y(n,p) , \mathbb{Z})$ , other than what is implied by the above results.]

I was thinking recently about a cubical analogue of the Linial-Meshulam set up. Define $Z(n,p)$ to be the one-skeleton of the $n$ -dimensional cube with each square two-dimensional face inserted independently with probability $p$ . This should be the cubical analogue of the Linial-Mesulam model? So what are the thresholds for the vanishing of $H_1 ( Z(n,p) , \mathbb{Z} / 2)$ and $\pi_1 ( Z(n,p) )$ ?

I just did some “back of the envelope” calculations which surprised me. It looks like $p$ must be much larger (in particular bounded away from zero) before either homology or homotopy is killed. Here is what I think probably happens. For the sake of simplicity assume here that $p$ is constant, although in realty there are $o(1)$ terms that I am suppressing.

(1) If $p < \log{2}$ then a.a.s $H_1 ( Z(n,p) , \mathbb{Z} /2 ) \neq 0$ , and if $p > \log{2}$ then a.a.s $H_1 ( Z(n,p) , \mathbb{Z} /2 ) = 0$ .

(2) If $p < (\log{2})^{1/4}$ then a.a.s. $\pi_1 ( Z(n,p) ) \neq 0$ , and if $p > (\log{2})^{1/4}$ then a.a.s. $\pi_1 ( Z(n,p) ) = 0$ .

Perhaps in a future post I can explain where the numbers $\log{2} \approx 0.69315$ and $(\log{2})^{1/4} \approx 0.91244$ come from. Or in the meantime, I would be grateful for any corroborating computations or counterexamples.

About these ads

mathematical musings

A conjecture concerning random cubical complexes

Like this:

Leave a Reply Cancel reply

Follow “mathematical musings”