Finding Long Cycles in Percolated Expander Graphs
Abstract
ABSTRACT Given a graph , the percolated graph is formed by retaining each edge independently with probability . Collares, Diskin, Erde, and Krivelevich initiated the study of large structures in percolated single‐scale vertex‐expander graphs, wherein every set of exactly vertices of has at least neighbors before percolation. We extend their result to a conjectured stronger form, proving that if and is a graph on at least vertices which expands as above, then contains a cycle of length with probability at least as .
Fields of Study & Subjects
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Data Mining Algorithms and Applications
Publication details
- Journal / source
- Random Structures and Algorithms
- Volume
- 68
- Issue
- 3
- Publication date
- 1 May 2026
- Language
- EN