An improved upper bound for the multicolour Ramsey number of odd cycles

Maria Axenovich, Wouter Cames van Batenburg, Oliver Janzer, Lukas Michel, Mathieu Rundström · 2025

Read An improved upper bound for the multicolour Ramsey number of odd cycles by Maria Axenovich, Wouter Cames van Batenburg, Oliver Janzer, Lukas Michel, Mathieu Rundström (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-17981.txt.

Introduction

Maria Axenovich and four co-authors improve a long-standing bound in Ramsey theory, a field about forced patterns in colored networks. The question asks how large a complete network must be so that any coloring with a set number of colors yields a one-color odd cycle of fixed length. A conjecture by Fox predicted the sharper bound they now prove.

Their upper bound is the first gain in the exponent beyond a constant factor since work from 1973. Progress on this problem had stalled for decades at that basic level. For combinatorics readers, the paper closes a named conjecture and resets the scale for multicolor cycle problems.

Catalog record

CREATORMaria Axenovich, Wouter Cames van Batenburg, Oliver Janzer, Lukas Michel, Mathieu Rundström
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE11 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-17981

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An improved upper bound for the multicolour Ramsey number of odd cycles Maria Axenovich, Wouter Cames van Batenburg, Oliver Janzer, Lukas Michel, Mathieu Rundström Abstract We show that the k k -colour Ramsey number of an odd cycle of length 2 ​ ℓ + 1 2\ell+1 is at most ( 4 ​ ℓ ) k ⋅ k k / ℓ (4\ell)^{k}\cdot k^{k/\ell} . This proves a conjecture of Fox and is the first improvement in the exponent that goes beyond an absolute constant factor since the work of Bondy and Erdős from 1973. 1 Introduction The k -colour Ramsey number R_{k}(H) of a graph H is the smallest integer n such that every k -edge-colouring of the complete graph K_{n} contains a monochromatic copy of H . For the triangle, the notoriously difficult Schur-Erdős problem asks to determine the growth rate of R_{k}(C_{3}) . In 1916, Schur [ Sch16 ] showed that \Omega(2^{k})\leq R_{k}(C_{3})\leq\mathcal{O}(k!). Since then, the upper bound has remained unchanged up to small improvements to the constant factor, while the lower bound has been improved to \Omega(3.28^{k}) by Ageron, Casteras, Pellerin, Portella, Rimmel, and Tomasik [ ACP+21 ] . Erdős conjectured that R_{k}(C_{3})=2^{\Theta(k)} [ CG98 ] and offered monetary awards for proving this conjecture and solving some related problems. For longer odd cycles, Bondy and Erdős [ BE73 ] and Erdős and Graham [ EG73 ] obtained the bounds \ell\cdot 2^{k}+1\leq R_{k}(C_{2\ell+1})\leq 2\ell\cdot(k+2)!. If k is fixed, it turns out that the lower bound is sharp as Jenssen and Skokan [ JS21 ] proved that R_{k}(C_{2\ell+1})=\ell\cdot 2^{k}+1 for all sufficiently large \ell . However, this is not true if \ell is fixed. Indeed, Day and Johnson [ DJ17 ] showed that for all \ell there exists some \delta\coloneqq\delta(\ell)>0 such that R_{k}(C_{2\ell+1})\geq 2\ell\cdot(2+\delta)^{k-1} for all sufficiently large k . Usually, if the number of colours is large, longer odd cycles should be easier to find than shorter odd cycles. For instance, Fox [ Fox ] conjectured that for every \varepsilon>0 there exists some \ell such that R_{k}(C_{2\ell+1})\leq k^{\varepsilon k} for all sufficiently large k . Li [ Li09 ] even made the stronger conjecture that R_{k}(C_{2\ell+1})\leq o(k!^{1/\ell}) as k\to\infty . Nevertheless, the gap between these conjectures and the best upper bounds known remained large. Li [ Li09 ] proved that R_{k}(C_{5})\leq c^{k}\cdot\sqrt{k!} for some constant c , which was later extended by Lin and Chen [ LC19 ] to longer odd cycles by showing that for \ell\geq 2 we have R_{k}(C_{2\ell+1})\leq c^{k}\cdot\sqrt{k!} for some constant c that only depends on \ell . 1 1 1 These results were proved independently by Fox [ Fox ] , but were never published. Only under the wide open additional assumption that each Ramsey graph for R_{k}(C_{2\ell+1}) is nearly regular 2 2 2 That is, there is an absolute constant \varepsilon such that for all sufficiently large k , the minimum degree of every Ramsey graph for R_{k}(C_{2\ell+1}) is at least an \varepsilon -fraction of its average degree. , Li [ Li09 ] showed that this bound could be improved to R_{k}(C_{2\ell+1})\leq c^{k}\cdot k!^{1/\ell} . In this paper, we prove the conjecture of Fox. Theorem 1.1 . For k,\ell\in\mathbb{N} , R_{k}(C_{2\ell+1})\leq(4\ell-2)^{k}\cdot k^{k/\ell}+1. Using the well-known inequality (k/e)^{k}<k! , this bound implies that R_{k}(C_{2\ell+1})\leq c^{k}\cdot k!^{1/\ell}+1 for c\coloneqq(4\ell-2)e^{1/\ell} , and so this establishes the conditional upper bound of Li unconditionally. In addition to finding a monochromatic odd cycle of a specific length, there has also been considerable interest in finding any short monochromatic odd cycle. It is easy to see that there is a k -edge-colouring of K_{2^{k}} without any monochromatic odd cycles, but that every k -edge-colouring of K_{2^{k}+1} contains such a cycle. Motivated by this, in 1973, Erdős and Graham [ EG73 , Question (iii) in Section 6] asked for the smallest integer L(k) such that every k -edge-colouring of K_{2^{k}+1} contains a monochromatic odd cycle of length at most L(k) . Day and Johnson [ DJ17 ] proved that L(k)\geq 2^{\Omega(\sqrt{\log k})} . Recently, Girão and Hunter [ GH24 ] obtained the first non-trivial upper bound, showing that L(k)\leq(2^{k}+1)/k^{1-o(1)} . Using an algebraic approach, Janzer and Yip [ JY25 ] improved this to L(k)\leq\mathcal{O}(k^{3/2}\cdot 2^{k/2}) . Both Girão and Hunter [ GH24 ] and Janzer and Yip [ JY25 ] also discussed the more general problem of finding short monochromatic odd cycles in colourings of complete graphs with more vertices. In the regime where the number of vertices is (2+\delta)^{k} for some small \delta>0 , the methods of both papers can guarantee a monochromatic odd cycle of length at most \mathcal{O}_{\delta}(k) . The dependence on \delta is better in [ JY25 ] , where the length of the cycle is \mathcal{O}(\delta^{-1/2}\cdot k) if \delta<1 . With our method, we can find significantly shorter monochromatic odd cycles, unless \delta tends to 0 very quickly. Theorem 1.2 . For k\in\mathbb{N} and b>2 , every k -edge-colouring of K_{n} with n>b^{k} contains a monochromatic odd cycle of length at most 2\lceil\log_{b/2}k\rceil+1 . In particular, if b=2+\delta for 0<\delta<1 , this result guarantees a cycle of length \mathcal{O}(\delta^{-1}\cdot\log k) . In addition, the result also applies to larger values of b . If b=k^{\varepsilon} , this yields a result similar to Theorem 1.1 , but without controlling the exact cycle length. We remark that Theorem 1.2 does not give any non-trivial result for the Erdős–Graham problem, where \delta\approx 1/(k\cdot 2^{k-1}) . Notation. For an edge-coloured graph, let N_{c}^{i}(v) be the set of all vertices u such that the shortest path of colour c from v to u has length i , and write N_{c}(v)\coloneqq N_{c}^{1}(v) and N_{c}^{\leq\ell}(v)\coloneqq\bigcup_{i=0}^{\ell}N_{c}^{i}(v) . For an uncoloured graph, N^{i}(v) denotes the set of vertices at distance exactly i from v . 2 Neighbourhoods with small chromatic number In Section 3 , we prove Theorems 1.1 and 1.2 using the following key lemma. This result bounds the number of vertices of a k -edge-coloured complete graph as long as for every vertex v and every colour c , the subgraph of colour c induced by the neighbourhood N_{c}^{\leq\ell}(v) has small chromatic number (which is the case if the colouring does not contain a monochromatic odd cycle of length 2\ell+1 ). In fact, we prove this lemma for k -local-edge-colourings , which are edge-colourings where at most k colours are incident to each vertex. Lemma 2.1 . Let k,\ell,\chi\in\mathbb{N} . Consider a k -local-edge-colouring of a complete graph K_{n} such that for every vertex v\in V(K_{n}) and every colour c , the subgraph of colour c induced by N_{c}^{\leq\ell}(v) in K_{n} has chromatic number at most \chi . Then, n\leq\chi^{k}\cdot k^{k/\ell} . Let G\coloneqq K_{n} . Define the weight of a vertex v\in V(G) as w(v)\coloneqq(\chi\cdot k^{1/\ell})^{-d_{\textrm{col}}(v)} where d_{\textrm{col}}(v) denotes the number of colours incident to v , and define the weight of a subset of vertices U\subseteq V(G) as w(U)\coloneqq\sum_{v\in U}w(v) . Note that w(v)\geq\chi^{-k}\cdot k^{-k/\ell} for every vertex v\in V(G) , and so w(V(G))\geq n\cdot\chi^{-k}\cdot k^{-k/\ell} . To show that n\leq\chi^{k}\cdot k^{k/\ell} , it therefore suffices to prove that w(V(G))\leq 1 . We will prove this by induction on the number of vertices of G . The case \lvert V(G)\rvert=1 is trivial, so suppose that \lvert V(G)\rvert\geq 2 . Let v\in

Read the complete text