Induced Size-Ramsey Numbers of Odd Cycles via Spread Measures

@misc{wang2026induced,
  title = {{Induced Size-Ramsey Numbers of Odd Cycles via Spread Measures}},
  author = {Lanchao Wang and Xiaolin Wang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.06481},
  eprint = {2609.06481},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.06481},
}

TY  - UNPB
TI  - Induced Size-Ramsey Numbers of Odd Cycles via Spread Measures
AU  - Lanchao Wang
AU  - Xiaolin Wang
PY  - 2026
DA  - 2026/10/25
PB  - arXiv
DO  - 10.48550/arxiv.2609.06481
UR  - https://arxiv.org/abs/2609.06481
AB  - We prove that, for every k≥2 and every sufficiently large odd n, the induced size--Ramsey number of C_n satisfies R̂_ind(C_n;k)=e^Θ(k)n. This improves the previous upper bound of e^O(klog k)n and resolves a conjecture of Bradač, Draganić and Sudakov. We obtain this result by proving a stronger form of their odd-hole gadget conjecture: we construct a graph with e^O(k) edges whose every k-edge-colouring contains a monochromatic induced odd cycle of length O(log k). Our proof develops a spread-based approach to finding induced cycles. The key idea is to place spread probability weights directly on families of candidate cycles and control their possible chords through a quadratic chord score. Combining this with random sparsification and hypergraph containers yields a sparse host graph that works for every k-edge-colouring.
ER  -