Isoperimetric inequalities and supercritical percolation on high-dimensional graphs (Q6607836)

This paper is about random subgraph models, where a particular host graph \(G\) on \(n\) vertices is taken and each edge is retained with probability \(p=p(n)\) independently of all other edges. (For \(G=K_{n}\) we get the standard Erdős-Rényi random graph). The aim is to understand the structure of the random subgraph, with as so often in random graph theory the structure of the largest component (the \lq giant component \rq) \(L_{1}\) being of interest. This structure is closely linked with isoperimetric inequalities in the giant component, themselves linked to isoperimetric properties of the host graph. In this paper the host graph will be a high-dimensional product of (suitable) base graphs; the relevant notion of product here is the Cartesian (or box) product. The Cartesian product of \(t\) graphs \(G^{(i)}=(V_{i},E_{i})\) for \(1\leq i\leq t\), denoted \(\square_{i=1}^{t}G^{(i)}\), has vertex set \(V_{1}\times V_{2}\times \ldots \times V_{t}\) with two vertices \((v_{1},v_{2},\ldots v_{t})\) and \((w_{1},w_{2},\ldots w_{t})\) adjacent if and only if \(w_{i}=v_{i}\) for all but one \(j\in \{1,2,\ldots t\}\) and we also have \(v_{j}\) adjacent to \(w_{j}\) in \(G^{(j)}\). An archetypal example is the host graph being the hypercube, which is the Cartesian product (often simply called product in the paper under review) of several copies of a single edge \(K_{2}\). There is known theory relating the Isoperimetric properties of the host graph to those of the base graphs, and we aim to find analogues of the well-known Harper's inequality in the hypercube. A key measure of how good an isoperimetric inequality we have will be the quantity \(i_{k}(G)=\min_{S\subseteq V(G), \vert S\vert=k}\vert \partial S\vert/k\) where, as usual, the boundary \(\partial S\) is the set of edges with one endpoint in \(S\) and the other outside \(S\). (The usual edge-isoperimetric constant \(i(G)=\min_{k\leq \lfloor n/2 \rfloor}i_{k}(G)\)).\par For example, the authors prove (Theorem 1) a theorem that if the base graphs \(G^{(j)}\) are \(d_{j}\)-regular graphs with \(1<\vert V(G^{(j)})\vert \leq C\) for every \(j\), then, letting \(d=\sum_{i=1}^{t}d_{i}\), be the degree of the regular graph \(G=\square_{i=1}^{t}G^{(i)}\), we have \(i_{k}(G)\geq \sum_{i=1}^{t}d_{i}-(C-1)\log_{2}(k)\). Observe that when \(C=2\) we recover the classical Harper's inequality for the hypercube. They also prove a result (Theorem 2) with the same bound on the size of the base graphs and the assumption that the base graphs are connected but no regularity assumption; this bound is \(i_{k}(G)\geq \log_{C}(n/k)/(C-1)\).\par We now move to results on the random subgraph: Theorem 3 is, in essence, a lower bound on the size \(\vert \partial_{G_{p}}(S)\vert \) of the boundary in the random subgraph of a set \(S\) in \(L_{1}\) when \(p\) is in the supercritical regime \(p=(1+\epsilon)/d\); for example, if \(k\leq 3\epsilon n/2\) and \(S\subseteq V(L_{1})\) with \(\vert S\vert=k\), we have \(\mathbf{whp} \vert \partial_{G_{p}}(S)\vert \geq c(\epsilon)k/(d\ln(d))\). This implies a lower bound of the form \(\Omega(1/(d^{2}\log(d))\) for vertex-expansion of arbitrary subsets of \(L_{1}\). Improvements are given when the set \(S\) is linear-sized (i.e. contains a strictly positive proportion of the vertices of the component), and when the set \(S\) is connected Theorem 4 gives another improvement in these lower bounds Theorem 5 is a consequence of previous parts; its essence is that typically \(L_{1}\) contains a linear-sized good expander at all scales., and Theorem 6 gives upper bounds on the diameter and mixing time of a lazy random walk on \(L_{1}\), and a lower bound on its circumference. \par Techniques include entropy arguments and careful analysis of a subgraph of \(L_{1}\) called the early giant. The authors also note several open questions.