Finding long cycles in a percolated expander graphs

2025/06/13 by Hollom, Lawrence
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2506.12162

Abstract

Given a graph G, the percolated graph G_p has each edge independently retained with probability p. Collares, Diskin, Erde, and Krivelevich initiated the study of large structures in percolated single-scale vertex expander graphs, wherein every set of exactly k vertices of G has at least dk neighbours before percolation. We extend their result to a conjectured stronger form, proving that if p = (1+ε)/d and G is a graph on at least k vertices which expands as above, then G_p contains a cycle of length Ω_ε(kd) with probability at least 1-exp(-Ω_ε(k/d)) as k→∞.

Citations

• Long cycles in percolated expanders
• Percolation through Isoperimetry
• Percolation on High-dimensional Product Graphs
• Expanders - how to find them, and what to find in them
• Long paths and cycles in random subgraphs of H-free graphs
• The phase transition in random graphs - a simple proof

Related

• Long cycles in percolated expanders
• Percolation on finite graphs and isoperimetric inequalities
• Long cycles in locally expanding graphs, with applications
• Cycle lengths in expanding graphs
• Cycle lengths modulo k in expanders