2023/08/20 by Diskin, Sahar, Erde, Joshua, Kang, Mihyun +1 · 1 citation
#05C80 #60K35 #82B43 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2308.10267
We provide a sufficient condition on the isoperimetric properties of a regular graph G of growing degree d, under which the random subgraph Gp typically undergoes a phase transition around p=(1)/(d) which resembles the emergence of a giant component in the binomial random graph model G(n,p). We further show that this condition is tight. More precisely, let d=ω(1), let ε>0 be a small enough constant, and let p ⋅ d=1+ε. We show that if C is sufficiently large and G is a d-regular n-vertex graph where every subset S⊆ V(G) of order at most (n)/(2) has edge-boundary of size at least C|S|, then Gp typically has a unique linear sized component, whose order is asymptotically y(ε)n, where y(ε) is the survival probability of a Galton-Watson tree with offspring distribution Po(1+ε). We further give examples to show that this result is tight both in terms of its dependence on C, and with respect to the order of the second-largest component. We also consider a more general setting, where we only control the expansion of sets up to size k. In this case, we show that if G is such that every subset S⊆ V(G) of order at most k has edge-boundary of size at least d|S| and p is such that p⋅ d ≥ 1 + ε, then Gp typically contains a component of order Ω(k).