Spread Methods for Induced Cycles

Source abstract

We develop a spread-based approach to finding induced cycles and apply it to two problems. First, we resolve the odd-hole gadget conjecture of Bradač, Draganić and Sudakov by constructing an $e^{O(k)}$-edge graph whose every $k$-edge-colouring contains a monochromatic induced odd cycle of length $O(\log k)$. As a consequence, for every $k\ge2$ and every sufficiently large odd $n$, $$\widehat R_{\mathrm{ind}}(C_n;k)=e^{Θ(k)}n.$$ The proof uses spread probability weights together with hypergraph containers. Second, we prove that for every sufficiently large fixed $d$, with high probability the largest hole in the random $d$-regular graph $G_{n,d}$ has order $Θ(n\log d/d)$, resolving a problem of Frieze. Although the two proofs use different mechanisms, both begin with a well-distributed auxiliary object and use it to control the extra edges that could destroy inducedness.