Short monochromatic odd cycles
Mathematical Proceedings of the Cambridge Philosophical Society · 2026-07 · 181 (1) · 781-788
DOI: 10.1017/s0305004125101801 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Proceedings of the Cambridge Philosophical Society, online erschienen am 27.03.2026. Verfasst von OLIVER JANZER und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 17 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
It is easy to see that every k -edge-colouring of the complete graph on 2 Superscript k Baseline plus 1 2 k + 1 $2^k+1$ vertices contains a monochromatic odd cycle. In 1973, Erdős and Graham asked to estimate the smallest L ( k ) such that every k -edge-colouring of upper K Subscript 2 Sub Superscript k Subscript plus 1 K 2 k + 1 $K_{2^k+1}$ contains a monochromatic odd cycle of length at most L ( k ). Recently, Girão and Hunter obtained the first nontrivial upper bound by showing that upper L left parenthesis k right parenthesis equals upper O left parenthesis 2 Superscript k Baseline divided by left parenthesis k Superscript 1 minus o left parenthesis 1 right parenthesis Baseline right parenthesis right parenthesis L ( k ) = O ( 2 k / ( k 1 − o ( 1 ) ) ) $L(k)=O({2^k}/({k^{1-o(1)}}))$ , which improves the trivial bound by a polynomial factor. We obtain an exponential improvement by proving that upper L left parenthesis k right parenthesis equals upper O left parenthesis k Superscript 3 divided by 2 Baseline 2 Superscript k divided by 2 Baseline right parenthesis L ( k ) = O ( k 3 / 2 2 k / 2 ) $L(k)=O(k^{3/2}2^{k/2})$ . Our proof combines tools from algebraic combinatorics and approximation theory.
Zitieren
APA
JANZER, O., & YIP, F. (2026). Short monochromatic odd cycles. Mathematical Proceedings of the Cambridge Philosophical Society, 181(1), 781-788. https://doi.org/10.1017/s0305004125101801
Vancouver
JANZER O, YIP F. Short monochromatic odd cycles. Mathematical Proceedings of the Cambridge Philosophical Society. 2026;181(1):781-788. doi:10.1017/s0305004125101801
BibTeX
@article{JANZER2026,
author = {JANZER, OLIVER and YIP, FREDY},
title = {Short monochromatic odd cycles},
journal = {Mathematical Proceedings of the Cambridge Philosophical Society},
year = {2026},
volume = {181},
number = {1},
pages = {781--788},
doi = {10.1017/s0305004125101801}
}
EUVIMED