Subdivision conjecture for percolated vertex expanders

Fix dNd\in\mathbb{N} and let HH be a graph of maximum degree 33. Let kNk\in\mathbb{N}, and let GG be an (=k,d)(=\hspace{-0.2em}k,d)-vertex expander, meaning that every set SV(G)S\subseteq V(G) with S=k|S|=k has at least dkdk external neighbors. For εε0(d)=dO(1)\varepsilon\geq\varepsilon_0(d)=d^{-O(1)}, set p=(1+ε)/dp=(1+\varepsilon)/d and let GpG_p be the percolated graph. Subdivision conjecture. With high probability, GpG_p contains a subdivision of HH. This is proposed as a significant strengthening of the paper's main long-cycle theorem; the precise dependence of the threshold ε0(d)\varepsilon_0(d) 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.