Topology of random 2-dimensional cubical complexes

We study a natural model of random $2$-dimensional cubical complex which is a subcomplex of an $n$-dimensional cube, and where every possible square $2$-face is included independently with probability $p$. Our main result exhibits a sharp threshold $p=1/2$ for homology vanishing as $n \to \infty$. This is a $2$-dimensional analogue of the Burtin and Erd\H{o}s--Spencer theorems characterizing the connectivity threshold for random graphs on the $1$-skeleton of the $n$-dimensional cube. Our main result can also be seen as a cubical counterpart to the Linial--Meshulam theorem for random $2$-dimensional simplicial complexes. However, the models exhibit strikingly different behaviors. We show that if $p > 1 - \sqrt{1/2} \approx 0.2929$, then with high probability the fundamental group is a free group with one generator for every maximal $1$-dimensional face. As a corollary, homology vanishing and simple connectivity have the same threshold, even in the strong ``hitting time'' sense. This is in contrast with the simplicial case, where the thresholds are far apart. The proof depends on an iterative algorithm for contracting cycles --- we show that with high probability the algorithm rapidly and dramatically simplifies the fundamental group, converging after only a few steps.