2024/04/04 by Sahar Diskin, Joshua Erde, Mihyun Kang +1
Mathematics · Psychology · #Combinatorics #Graph theory and applications #Inequality #Isoperimetric dimension #Isoperimetric inequality #Limits and Structures in Graph Theory #Mathematical analysis #Mathematics #Percolation (cognitive psychology) #Physics #Psychology #Stochastic processes and statistical mechanics #Supercritical fluid #Thermodynamics
paper · pdf · doi:10.1007/s00493-024-00089-0
crossref issued 2024/04/04 · crossref published 2024/04/04 · crossref published-online 2024/04/04 · openalex publication_date 2024/04/04 · crossref created 2024/04/04 · crossref deposited 2024/07/24 · crossref published-print 2024/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01 · crossref indexed 2026/08/05
Abstract 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>L</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> in supercritical percolation on these product graphs, that is, when p=(1+ε )/(d) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>=</mml:mo> <mml:mfrac> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:mfrac> </mml:mrow> </mml:math> , where d is the degree of the product graph and ε gt;0 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo>></mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> is a small enough constant. We show that typically L1 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>L</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> has edge-expansion Ω ( (1)/(dln d)) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mfenced> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>ln</mml:mo> <mml:mi>d</mml:mi> </mml:mrow> </mml:mfrac> </mml:mfenced> </mml:mrow> </mml:math> . Furthermore, we show that L1 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>L</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> likely contains a linear-sized subgraph with vertex-expansion Ω ( (1)/(dln d)) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mfenced> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>ln</mml:mo> <mml:mi>d</mml:mi> </mml:mrow> </mml:mfrac> </mml:mfenced> </mml:mrow> </mml:math> . 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>L</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> as well as the typical mixing time of a lazy random walk on L1 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>L</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> . Furthermore, we show the likely existence of a cycle of length Ω ( (n)/(dln d)) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mfenced> <mml:mfrac> <mml:mi>n</mml:mi> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>ln</mml:mo> <mml:mi>d</mml:mi> </mml:mrow> </mml:mfrac> </mml:mfenced> </mml:mrow> </mml:math> . 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>L</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> were previously only known to be polynomial in d .