{"id":"7d4d3ee2-6fa3-4088-be23-66a6684c9f01","arxiv_id":"2412.07708","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Every q-edge-colouring of K_{2^q+1} contains a monochromatic odd cycle of length O(2^q/q^{1-o(1)}), the first bound of the form o(2^q).","lead":"This paper proves the first non-trivial upper bound on the shortest guaranteed monochromatic odd cycle in every q-edge-colouring of the complete graph on 2^q+1 vertices. The result, L(q)=O(2^q/q^{1-o(1)}), breaks the trivial 2^q barrier for a question Erdős and Graham posed in 1973.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.3 is not proven as stated: the key inequality n·2^{-(1−ε)q} ≥ 2^{εq/2} fails for n=2^{q/2} unless ε≥1. The main theorem invokes this lemma, so the proof has a repairable gap.","rationale":"The reader's ACCEPT verdict identifies the bipartite-colouring characterization as the weakest assumption, but the proof of that standard fact is correct; the real soft spot is in Lemma 2.3, where the displayed inequality n·2^{-(1−ε)q} ≥ 2^{εq/2} does not follow from the hypotheses as written. Since Theorem 1.2 directly invokes this lemma, the proof has a gap. However, the gap is local and easily fixed: the application in Section 3 satisfies the stronger size condition n' ≥ 2^{q−1} and has δq → ∞, and then the proof of Lemma 2.3 itself yields |L| ≥ 2^{δq−1} ≥ 2^{δq/2}. The rest of the argument — the induction, Lemmas 2.1 and 2.2, and the small-component degree contradiction — checks out. For these reasons the central claim is very likely correct, but the paper should be accepted only after the statement and proof of Lemma 2.3 are corrected.","tokens_in":4789,"tokens_out":39855,"duration_ms":323201,"concrete_test":"Recompute the expectation bound in Lemma 2.3 under the stated hypothesis: set q=10, ε=0.2, n=2^{q/2}=32, and check whether the claimed lower bound 2^{εq/2}=2 follows from n·2^{-(1−ε)q}. Also verify the application in §3: with n' ≥ 2^{q−1} and δq → ∞, the proof's actual exponent δq−1 satisfies 2^{δq−1} ≥ 2^{δq/2}, so the main contradiction still works once the lemma is restated with the stronger hypothesis n ≥ 2^{q−1} (and εq ≥ 2).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 2, Lemma 2.3 asserts that if n ≥ 2^{q/2} and |A_i|+|B_i| ≤ (1−ε)n for each i, then there is a set L of size at least 2^{εq/2} with no cross edge between A_i and B_i for any i. The proof's expectation argument gives a lower bound of n·2^{-(1−ε)q} on the expected size of [n]\\U. The proof then claims this is ≥ 2^{εq/2}. That inequality is equivalent to n ≥ 2^{(1−ε/2)q}, which is not implied by n ≥ 2^{q/2} when ε < 1. For example, q=10, ε=0.2 gives n=2^{q/2}=32 and n·2^{-(1−ε)q} = 32·2^{-8} = 1/8, while the lemma promises a set of size at least 2. So the stated lemma is not established by the given argument. This is a genuine gap because the proof of Theorem 1.2 in Section 3 explicitly applies Lemma 2.3 to obtain |L| ≥ 2^{δq/2}. The gap is repairable: in the application n' ≥ 2^q/2 and δ > 1/q^{1−ε}, and the proof's actual bound n'·2^{-(1−δ)q} ≥ 2^{δq−1} is ≥ 2^{δq/2} for large q. Thus the central claim survives a modest correction to the lemma's hypothesis, but the paper as written relies on an unproved lemma.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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}.","tokens_in":5203,"tokens_out":28084,"duration_ms":249535,"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":[{"comment":"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":"Section 3, final paragraph"},{"comment":"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.","section":"Section 2, Lemma 2.3"}],"minor_comments":[{"comment":"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":"Lemma 2.1, proof"},{"comment":"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.","section":"Section 3, first paragraph"},{"comment":"'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":"Lemma 2.2, proof"},{"comment":"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}).","section":"Section 4, concluding remarks"},{"comment":"There are a few minor language issues, for example 'In here' and 'colouring KN' should be 'colouring of KN'.","section":"Abstract and introduction"}],"recommendation":"major_revision","confidential_remarks":"The reader's report that accompanies this manuscript recommends acceptance, but it appears to have overlooked a serious gap in the final step of the proof of Theorem 1.2. In my view the result is likely true and the paper is well worth publishing once the final contradiction is repaired; as written, however, the proof is incomplete. The Lemma 2.3 issue is a smaller, easily fixable gap. I would advise the editor to request a major revision and to ask the authors to provide a correct argument for the final step or to reformulate the proof so that the stated degree bound actually applies."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nThe headline: this is the first non-trivial upper bound on Erdős–Graham's L(q), and the main theorem is very likely correct. The proof has a real flaw in a stated lemma, but the flaw does not sink the core argument.\n\nWhat is genuinely new: Theorem 1.2 beats the trivial 2^q+1 barrier by q^{1-o(1)}, using a clean combination of BFS layering (Lemma 2.1), a random-sampling lemma (Lemma 2.3), and a short-odd-cycle conversion (Lemma 2.2). The induction is tidy and the result is a clear step beyond what Day–Johnson left open. The gap to their 2^{Ω(√log q)} lower bound is still large, so this is not a resolution, but it is the first upper bound of the right shape.\n\nThe soft spot is Lemma 2.3. The proof claims n·2^{-(1−ε)q} ≥ 2^{εq/2} from n ≥ 2^{q/2}. That inequality is equivalent to n ≥ 2^{q(1−ε/2)}, which is not implied. For ε < 1 the stated hypothesis is too weak; the expectation argument gives a much smaller lower bound than the lemma promises, so the lemma is not proven as stated. I don't have a counterexample in hand, but the proposition is unsupported as written. The saving grace is that the application in Section 3 uses n' ≥ 2^q/2 and δ > q^{ε-1}, and there the actual arithmetic gives |L| ≥ 2^{δq-1} ≥ 2^{δq/2} for large q. So Theorem 1.2 should survive after the lemma's hypothesis is strengthened to something like n ≥ 2^{q(1−ε/2)} and the proof is adjusted accordingly. The current text needs a non-trivial revision, not just a typo fix.\n\nEverything else checks out: the bipartite-colouring fact used in the induction is standard and true; the citations to Day–Johnson and Jenssen–Skokan are appropriate; there is no circularity and no fitted parameter. The writing is clear.\n\nVerdict: send it to referees — the result deserves scrutiny and likely publication after revision — but the referee should be told to focus on Lemma 2.3. I'd cite the main theorem once the correction is in place, and I'd bring it to the reading group either way.","headline":"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.","tokens_in":5703,"tokens_out":16367,"would_cite":true,"duration_ms":145904,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C55","05C15","05D40","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["monochromatic odd cycles","edge-coloured complete graphs","Erdős–Graham function","Ramsey theory","multicolour Ramsey numbers","probabilistic method","L(q) upper bound"],"falsifier":"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.","tokens_in":4638,"feed_emoji":"🔄","tokens_out":20266,"duration_ms":160610,"temperature":0.7,"pith_summary":"This paper establishes the first non-trivial upper bound on $L(q)$, the smallest length guaranteed for a monochromatic odd cycle in any $q$-edge-colouring of the complete graph on $2^q+1$ vertices. Previous work had only shown that $L(q)$ grows at least like $\\exp(\\Omega(\\sqrt{\\log q}))$; no upper bound of the form $o(2^q)$ was known. The authors show $L(q)=O(2^q/q^{1-o(1)})$, so for every $\\varepsilon>0$ and all large $q$ the guaranteed odd cycle has length at most $2^q/q^{1-\\varepsilon}$. This gives the first non-trivial upper bound on the Erdős–Graham function $L(q)$.","feed_headline":"Odd-cycle length in q-coloured graphs drops below 2^q","feed_subtitle":"Every q-colouring of the complete graph on 2^q+1 vertices has a monochromatic odd cycle of length at most 2^q/q^{1-o(1)}.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Poses the problem of determining $L(q)$ and supplies the bipartite-colouring observation (a $q$-colouring of $K_n$ with all colours bipartite exists iff $n \\leq 2^q$) that the induction uses.","marker":"[EG75]"},{"why":"Gives the lower bound $L(q) \\geq \\exp(\\Omega(\\sqrt{\\log q}))$ and the product-colouring construction used in the concluding remarks; its lower bound is the baseline the new upper bound beats.","marker":"[DJ17]"},{"why":"States the problem of whether $L(q)$ is unbounded; its resolution in [DJ17] gives the lower-bound comparison that the new upper bound improves.","marker":"[Chu97]"}],"fun_headline_variants":["Odd cycle bound: 2^q/q^{1-o(1)} in every q-coloring","Shaving a q^{1-o(1)} factor off odd cycle lengths","First non-trivial bound on odd cycle length in q-coloured complete graphs","Erdős–Graham problem: odd cycle bound improved by polynomial factor","Every q-colouring has an odd cycle of length O(2^q/q^{1-o(1)})"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Odd cycle bound: 2^q/q^{1-o(1)} in every q-coloring","Shaving a q^{1-o(1)} factor off odd cycle lengths","First non-trivial bound on odd cycle length in q-coloured complete graphs","Erdős–Graham problem: odd cycle bound improved by polynomial factor","Every q-colouring has an odd cycle of length O(2^q/q^{1-o(1)})"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001779,"raw_usage":{"total_tokens":6983,"prompt_tokens":886,"completion_tokens":6097,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":502,"completion_tokens_details":{"reasoning_tokens":5983}},"tokens_in":502,"tokens_out":6097,"duration_ms":47183,"temperature":1.0,"reasoning_tokens":5983,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:35:58.897424+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}