TY - JOUR
T1 - Isoperimetric Inequalities and Supercritical Percolation on High-Dimensional Graphs
AU - Diskin, Sahar
AU - Erde, Joshua
AU - Kang, Mihyun
AU - Krivelevich, Michael
N1 - Publisher Copyright:
© The Author(s) 2024.
PY - 2024/8
Y1 - 2024/8
N2 - It is known that many different types of finite random subgraph models undergo quantitatively similar phase transitions around their percolation thresholds, and the proofs of these results rely on isoperimetric properties of the underlying host graph. Recently, the authors showed that such a phase transition occurs in a large class of regular high-dimensional product graphs, generalising a classic result for the hypercube. In this paper we give new isoperimetric inequalities for such regular high-dimensional product graphs, which generalise the well-known isoperimetric inequality of Harper for the hypercube, and are asymptotically sharp for a wide range of set sizes. We then use these isoperimetric properties to investigate the structure of the giant component L1 in supercritical percolation on these product graphs, that is, when p=1+ϵd, where d is the degree of the product graph and ϵ>0 is a small enough constant. We show that typically L1 has edge-expansion Ω1dlnd. Furthermore, we show that L1 likely contains a linear-sized subgraph with vertex-expansion Ω1dlnd. These results are best possible up to the logarithmic factor in d. Using these likely expansion properties, we determine, up to small polylogarithmic factors in d, the likely diameter of L1 as well as the typical mixing time of a lazy random walk on L1. Furthermore, we show the likely existence of a cycle of length Ωndlnd. These results not only generalise, but also improve substantially upon the known bounds in the case of the hypercube, where in particular the likely diameter and typical mixing time of L1 were previously only known to be polynomial in d.
AB - It is known that many different types of finite random subgraph models undergo quantitatively similar phase transitions around their percolation thresholds, and the proofs of these results rely on isoperimetric properties of the underlying host graph. Recently, the authors showed that such a phase transition occurs in a large class of regular high-dimensional product graphs, generalising a classic result for the hypercube. In this paper we give new isoperimetric inequalities for such regular high-dimensional product graphs, which generalise the well-known isoperimetric inequality of Harper for the hypercube, and are asymptotically sharp for a wide range of set sizes. We then use these isoperimetric properties to investigate the structure of the giant component L1 in supercritical percolation on these product graphs, that is, when p=1+ϵd, where d is the degree of the product graph and ϵ>0 is a small enough constant. We show that typically L1 has edge-expansion Ω1dlnd. Furthermore, we show that L1 likely contains a linear-sized subgraph with vertex-expansion Ω1dlnd. These results are best possible up to the logarithmic factor in d. Using these likely expansion properties, we determine, up to small polylogarithmic factors in d, the likely diameter of L1 as well as the typical mixing time of a lazy random walk on L1. Furthermore, we show the likely existence of a cycle of length Ωndlnd. These results not only generalise, but also improve substantially upon the known bounds in the case of the hypercube, where in particular the likely diameter and typical mixing time of L1 were previously only known to be polynomial in d.
KW - Bond percolation
KW - Giant component
KW - Graph expansion
KW - Isoperimetric inequalities
KW - Product graphs
UR - http://www.scopus.com/inward/record.url?scp=85189477646&partnerID=8YFLogxK
U2 - 10.1007/s00493-024-00089-0
DO - 10.1007/s00493-024-00089-0
M3 - Article
AN - SCOPUS:85189477646
SN - 0209-9683
VL - 44
SP - 741
EP - 784
JO - Combinatorica
JF - Combinatorica
IS - 4
ER -