Subdivision conjecture for percolated vertex expanders
Subdivision conjecture for percolated vertex expanders
Fix and let be a graph of maximum degree . Let , and let be an -vertex expander, meaning that every set with has at least external neighbors. For , set and let be the percolated graph. Subdivision conjecture. With high probability, contains a subdivision of . This is proposed as a significant strengthening of the paper's main long-cycle theorem; the precise dependence of the threshold is part of the conjecture.
Sources & referencesView supporting material
Primary source
Lawrence Hollom, “Finding long cycles in a percolated expander graphs”, arXiv:2506.12162 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.