Expansion in supercritical random subgraphs of the hypercube and its consequences (Q2105142)

This paper presents new results about the expansion and other structural properties of the giant component of the edge-percolated \(d\)-dimensional hypercube in the supercritical regime. More precisely, let us fix a positive integer \(d\) and \(\varepsilon>0\), consider the \(d\)-dimensional hypercube, and keep all its edges independently with probability \(p=\frac{1+\varepsilon}{d}\). We will denote the random graph obtained this way by \(Q_p^d\). Furthermore, let \(L_1\) be the largest connected component of \(Q_p^d\). The authors prove the following results about the giant component \(L_1\): (i) expansion property with expansion ratio \(\beta d^{-5}\). More precisely, they prove that there exists \(\beta>0\) such that with high probability \(L_1\) is \(\beta d^{-5}\)-expander, meaning that for every set of vertices \(S\) with \(|S|\leq |V(G)|/2\) we have that the number of neighbors of \(S\) is at least \(\beta d^{-5}\) times the size of \(S\); (ii) there exists an almost spanning subgraph of \(Q_p^d\) which is a \(\beta d^{-2}/ \log d\)-expander; (iii) with high probability, the mixing time of the lazy random walk on \(L_1\) is \(O(d^{11})\); (iv) with high probability, the diameter of the giant component \(L_1\) is \(O(d^3)\); (v) lower bounds on the circumference and Hadwiger number of \(L_1\). The properties of the mixing time, diameter, circumference, and Hadwiger number all follow from the expansion properties, either as a consequence, using well-known results on the connection of expanders and mixing time, or more directly from the proof. Hence, the key point of the paper is to find a way to show that the giant component is a good expander. In order to do this, the authors use a sprinkling argument. In particular, they view \(Q_p^d\) as the union of two independent subgraphs, which are also percolated versions of the hypercube, but while one is still in the supercritical regime, the edge probability is very small in the other one. This second subgraph can be used to find large vertex-disjoint families of short paths that go between two fixed subsets of the vertices. Together with the larger family of edges in the first subgraph, a sequence of matching can be constructed, which then can be used to find the neighbors we need for the expansion property.