Spread Methods for Induced Cycles
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.06481
curl -X POST /api/v1/records/arxiv/2609.06481/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.06481/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'