REVIEW 2 major objections 5 minor 8 references
Monochromatic odd cycles in edge-coloured complete graphs
T0 review · 2 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read This paper proves that for every $\varepsilon>0$, every $q$-edge-colouring of $K_{2^q+1}$ contains a monochromatic odd cycle of length at most $2^q/q^{1-\varepsilon}$, giving the first non-trivial upper bound on the Erdős–Graham function…
desk verdict First o(2^q) upper bound on Erdős-Graham's L(q) with a genuinely nice proof, but Lemma 2.3 is not proven as stated and needs a corrected hypothesis before the paper is publishable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The proof rests on three lemmas. Lemma 2.1 (bipartite-deletion lemma): a graph on $n$ vertices with no odd cycle of length at most $2k+1$ can be made bipartite by deleting at most $(n \log_2 n)/k$ vertices, with every remaining component having radius at most $k$. Lemma 2.2 (radius-to-cycle lemma): a non-bipartite graph $F$ containing a subgraph whose components have radius at most $r$ contains an odd cycle of length at most $|V(F)\setminus V(H')|+(4r+1)m$. Lemma 2.3 (side-selection lemma): for $q$ pairs of disjoint sets $(A_i,B_i)$ with $|A_i|+|B_i| \le (1-\varepsilon)n$, there is a set $L$ of size at least $2^{\varepsilon q/2}$ with no edge of the form $a_i b_i$ for any $i$. The induction uses these to force a monochromatic odd cycle of length $O(2^q/q^{1-\varepsilon})$ or a contradiction.
What would settle it
A construction that would refute the theorem is a sequence of $q$-edge-colourings of $K_{2^q+1}$, for arbitrarily large $q$, in which every monochromatic odd cycle has length at least $2^q / q^{1-\delta}$ for some fixed $\delta>0$; the existence of such colourings would contradict the claimed $O(2^q/q^{1-o(1)})$ bound.
Extended reading notes
Core claim
The central result, Theorem 1.2, states that for every $\varepsilon>0$ there is $q_0$ such that for all $q>q_0$, every $q$-edge-colouring of the complete graph on $2^q+1$ vertices contains a monochromatic odd cycle of length at most $2^q/q^{1-\varepsilon}$. The proof is by induction on $q$. If some colour class is bipartite, the standard fact that $q$ bipartite colour classes can cover at most $2^q$ vertices allows the induction hypothesis to apply on a smaller complete graph. If every colour class is non-bipartite, the authors delete a small vertex set $S$ so that each remaining colour class is bipartite with connected components of radius $O(q^3)$; then a probabilistic side-selection lemma produces a large set $L$ with no edge in any colour, and the union of the remaining small components has maximum degree too small to cover the edges of $L$, a contradiction that forces a short odd cycle through Lemma 2.2.
Load-bearing premise
The load-bearing premise is the standard, unproved fact that a complete graph whose edges can be split into $q$ classes, each containing no odd cycle, has at most $2^q$ vertices; the induction relies on this reduction when a colour class has no odd cycle and the proof's final contradiction uses it as well.
Editorial extensions
If this is right
- The Erdős–Graham function satisfies $L(q) \leq O(2^q / q^{1-o(1)})$, so for large $q$ every $q$-edge-colouring of $K_{2^q+1}$ has a monochromatic odd cycle shorter than $2^q$ by a factor of $q^{1-o(1)}$.
- This is the first upper bound of the form $o(2^q)$; the gap to the best known lower bound $\exp(\Omega(\sqrt{\log q}))$ remains.
- For complete graphs on more than $2^q$ vertices, Proposition 4.1 gives $L(q,(1+\delta)2^q) \leq O(q^2 \delta^{-1})$ for every $\delta\in(0,1)$.
- A corollary stated in the paper: any $n$-vertex graph with no odd cycle of length at most $2k+1$ has an independent set of size at least $(1/2)(n - n^{-1/k})$, yielding $L(q,(2+\varepsilon)^q) \leq C_\varepsilon q + O_\varepsilon(1)$ for each fixed $\varepsilon>0$.
Reading between the lines
- The side-selection lemma (Lemma 2.3) may be reusable in other multicolour problems where one wants a large set avoiding forbidden cross edges; the authors do not pursue this.
- The bound $L(q)=O(2^q/q^{1-o(1)})$ may be far from the truth; by analogy with the lower bound, one might conjecture $L(q)=2^q/q^{\Theta(1)}$, but the paper makes no such conjecture.
- A natural next test is whether the factor $q^{1-o(1)}$ can be strengthened to a fixed power of $q$ using the same technique; the proof's explicit constants leave room for optimisation.
- The independent-set corollary suggests a bridge to extremal results on graphs of large odd girth, which could be explored in future work.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies L(q), the smallest integer ℓ such that every q-edge-colouring of K_{2^q+1} contains a monochromatic odd cycle of length at most ℓ. This quantity was introduced by Erdős and Graham. The main theorem claims L(q) = O(2^q/q^{1-o(1)}), which would be the first non-trivial upper bound, complementing the Day–Johnson lower bound. The proof uses an inductive structure: if some colour class is bipartite, the colour count reduces; otherwise, a lemma deletes a small set of vertices so that every colour class becomes bipartite with components of radius O(q^3). A second lemma then handles the case where the small deleted components are few, while the main remaining case uses a probabilistic lemma to find a large set of vertices free of cross edges in every colour outside the small components, intending to derive a contradiction from the small component size. A final proposition gives a stronger bound for K_{(1+δ)2^q}.
Significance. If Theorem 1.2 is correct, it is a genuinely new quantitative result for a long-standing Erdős–Graham problem, improving the trivial O(2^q) bound and giving the first o(2^q) upper bound. The overall strategy is natural and the preliminary lemmas are mostly elementary. The paper also makes a clear and useful connection to the Day–Johnson lower bound and offers a stronger statement for complete graphs with (1+δ)2^q vertices. However, the current manuscript contains two significant gaps in the proof of the main theorem; the final contradiction in Section 3 is not justified as written, and Lemma 2.3 is not proved under its stated hypothesis. These issues are repairable in principle, but the present proof is incomplete.
major comments (2)
- [Section 3, final paragraph] The contradiction after Lemma 2.3 is not established. Lemma 2.3 guarantees that for each colour i, the set L contains no edge of colour i with both endpoints in V' \ V(B_i). For an edge of colour i with exactly one endpoint in V(B_i), the edge is allowed but is not an edge inside a small component. Thus the statement 'all the edges in L must be covered using the connected components from B_1,...,B_q' does not mean the complete graph on L is contained in the union of those components, and the maximum degree of that union (at most q·4q^{10}) does not limit how many edges of K_L can be incident to V(B_i). In fact, if the sets V(B_i) cover all but at most one vertex of L, every edge has at least one endpoint in some V(B_i) and the covering condition alone presents no obstruction. Hence the proof of Theorem 1.2 is incomplete at this load-bearing step; a different argument is needed.
- [Section 2, Lemma 2.3] The proof's final inequality n·2^{-(1-ε)q} ≥ 2^{εq/2} does not follow from the hypothesis n ≥ 2^{q/2}. It requires n ≥ 2^{(1-ε/2)q}, which is not implied when ε < 1 (e.g., n = 2^{q/2}). In the application in Section 3 the stronger bound n' ≥ 2^q/2 and δ q large do make the inequality hold, but the lemma as stated is unproved. The statement should either strengthen the hypothesis to n ≥ 2^{(1-ε/2)q} or record the weaker conclusion n·2^{-(1-ε)q}, and the application should verify that weaker bound explicitly.
minor comments (5)
- [Lemma 2.1, proof] The displayed inequality |N^{(j)}(x)| ≤ n^{1/k}|N^{≤j-1}(x)| should be |N^{(j)}(x)| ≤ ε|N^{≤j-1}(x)|; the printed n^{1/k} is a typo that would break the bound |S| ≤ εn.
- [Section 3, first paragraph] The case in which some colour class already contains an odd cycle of length at most 2k+1 (with k = 8q^3) should be dismissed explicitly before assuming Lemma 2.1 can be applied, since such a cycle already meets the desired bound.
- [Lemma 2.2, proof] 'Distance in C' is used to mean the length of the shorter of the two paths on the cycle; please state this to avoid ambiguity with graph distance in C.
- [Section 4, concluding remarks] The corollary's independent set bound '(1/2)(n - n^{-1/k})' appears to be a typo; combining the stated bound |S| ≤ (1 - n^{-1/k})n with bipartition gives an independent set of size at least (1/2)n^{1-1/k} (or similar), not (1/2)(n - n^{-1/k}).
- [Abstract and introduction] There are a few minor language issues, for example 'In here' and 'colouring KN' should be 'colouring of KN'.
Circularity Check
No significant circularity: the main theorem is proved from self-contained lemmas, with external references used only for context.
full rationale
The derivation chain for Theorem 1.2 is self-contained rather than circular. The proof proceeds by induction on q, and the only structural input is the standard elementary fact that a complete graph whose edges are coloured with q colours, each colour class bipartite, has at most 2^q vertices. This fact is used to pass to a subgraph of size at least 2^{q-1}+1 when a colour class is bipartite; it is a short pigeonhole/binary-vector argument and is not equivalent to the theorem being proved. The main lemmas (Lemma 2.1, Lemma 2.2, and Lemma 2.3) are proved directly in the paper: Lemma 2.3 is a probabilistic expectation argument and does not import its conclusion from the theorem, from a fitted parameter, or from a citation. The cited works (Day--Johnson, Jenssen--Skokan, etc.) appear as context, lower bounds, or remarks, and none is used as a load-bearing input to the upper-bound proof. There are no self-citations by the authors, so no self-citation chain forces the result. No empirical prediction is fitted and then reported as a prediction. A non-circular caveat is worth noting: the proof of Lemma 2.3 as printed contains a numerical inequality, n*2^{-(1-epsilon)q} >= 2^{epsilon q/2}, that is not implied by the stated hypothesis n >= 2^{q/2}; this is a correctness/repair issue in the lemma's statement or proof, not a circularity, and in the main application n' is actually about 2^q, where the inequality is valid. This gap does not affect the circularity score.
Assumptions & free parameters
free parameters (2)
- k = 8q^3
- C(ε)
assumptions (3)
- standard math A graph with no odd cycle is bipartite
- standard math A complete graph on n vertices can be q-edge-coloured with every colour bipartite if and only if n ≤ 2^q
- standard math Bernoulli's inequality (1+x)^r ≥ 1+xr for x≥-1, r≥1
Cite this review
Pith. "Pith review of Monochromatic odd cycles in edge-coloured complete graphs." pith.science (2026). https://pith.science/paper/CBP4HF52
@misc{pith2026241207708,
author = {Pith},
title = {Pith review of: Monochromatic odd cycles in edge-coloured complete graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/CBP4HF52}},
note = {Machine review of arXiv:2412.07708}
}
abstract
It is easy to see that every $q$-edge-colouring of the complete graph on $2^q+1$ vertices must contain a monochromatic odd cycle. A natural question raised by Erd\H{o}s and Graham in $1973$ asks for the smallest $L(q)$ such that every $q$-edge-colouring of $K_{2^q+1}$ must contain a monochromatic odd cycle of length at most $L(q)$. In here, we show that $L(q)=O\left(\frac{2^q}{q^{1-o(1)}}\right)$ giving the first non-trivial upper bound on $L(q)$.
Reference graph
Works this paper leans on
-
[1]
P. Balister, B. Bollob\'as, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe, and M. Tiba. Upper bounds for multicolour R amsey numbers. ar X iv:2410.17197
- [2]
-
[3]
F. R. K. Chung. Open problems of P aul E rd o s in graph theory. Journal of Graph Theory , 25(1):3--36, 1997
work page 1997
- [4]
-
[5]
P. Erd o s and L. R. Graham. On partition theorems for finite graphs. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd o s on his 60th birthday) Vol I. , volume 10. Colloq. Math. Soc. J\'anos Bolyai, 1975
work page 1973
-
[6]
M. Jenssen and J. Skokan. Exact R amsey numbers of odd cycles via nonlinear optimisation. Advances in Mathematics , 376(107444), 2021
work page 2021
- [7]
- [8]
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.