pith. sign in

arxiv: 2605.07322 · v1 · submitted 2026-05-08 · 🧮 math.CO

New results on the odd- and unique-Ramsey numbers

Shagnik Das , Ying-Sian Wu This is my paper

Pith reviewed 2026-05-11 01:07 UTC · model grok-4.3

classification 🧮 math.CO
keywords odd-Ramsey numbersunique-Ramsey numbersbipartite graphsHamilton cyclesedge coloringsRamsey theorylower bounds
0
0 comments X

The pith

Odd-Ramsey numbers for K_{s,t} with s odd and t even are at least n to a positive power depending on s and t.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives explicit lower bounds showing that certain odd-Ramsey numbers grow polynomially in the size of the host graph. It proves that r_odd(n, K_{s,t}) exceeds n raised to 1 over (s/2 plus 1 over 2 times floor of t/8) when s is odd and at most t, which is asymptotically tight in the logarithmic sense for fixed s and large t. It also establishes that the unique-Ramsey number r_u(n, C_n) is larger than n/4, creating a polynomial separation from the corresponding odd-Ramsey number, and that any host graph with minimum degree at least n/2 + 2 forces the odd-Ramsey number of Hamilton cycles to be at least 2.

Core claim

We show r_odd(n, K_{s,t}) > n^{1/(s/2 + 1/(2 floor(t/8)))} when s ≤ t, s odd and t even. We show r_u(n, C_n) > n/4. In any host graph with minimum degree at least n/2 + 2 the odd-Ramsey number of Hamilton cycles is non-trivial.

What carries the argument

The odd-Ramsey number r_odd(n, H), defined as the smallest number of colors in an edge-coloring of K_n such that every copy of H contains at least one color appearing an odd number of times.

If this is right

  • For fixed odd s and even t growing, the exponent on n approaches 2/s and the bound becomes log-asymptotically tight.
  • The unique-Ramsey number for cycles is strictly larger than the odd-Ramsey number by a polynomial factor.
  • The minimum-degree condition n/2 + 2 is sufficient to guarantee that at least two colors are needed for any odd-Ramsey coloring of Hamilton cycles.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The parity restrictions suggest that similar polynomial growth may hold for other unbalanced bipartite graphs when the part sizes satisfy matching parity.
  • The gap between odd- and unique-Ramsey numbers for cycles raises the question of whether larger gaps exist for other graphs such as trees or grids.
  • The super-Dirac host-graph result may extend to other dense graph classes where Hamilton cycles are forced.

Load-bearing premise

The constructions and proofs require the stated parity conditions on the parts of the bipartite graph and the exact minimum-degree threshold n/2 + 2.

What would settle it

An edge-coloring of K_n that uses fewer than n to the power 1/(s/2 + 1/(2 floor(t/8))) colors in which every copy of K_{s,t} has even multiplicity in every color would falsify the main lower bound.

Figures

Figures reproduced from arXiv: 2605.07322 by Shagnik Das, Ying-Sian Wu.

Figure 1
Figure 1. Figure 1: The proof of Proposition 3.1. For Proposition 3.2, however, the proof of its counterpart in [7] no longer holds under our weaker minimum degree condition. The problem is that, after finding short paths Q1, Q2 like the Q in the previous proof, in the subgraph G′ , now δ(G′ ) might not be large enough to apply Lemma 3.3, so we cannot simply visit every remaining vertex by a Hamilton path P in G′ . To resolve… view at source ↗
Figure 2
Figure 2. Figure 2: Case 1.1 and C (1) , C (2). The odd-chromatic color pattern on abcdef a can be arbitrary. Case 1.2. More than half of the vertices in G′ have degree n ′/2. Since δ(G′ ) ≥ n ′/2, by Dirac’s theorem there is a Hamilton cycle in G′ , say C = aP1dP2a, P1 : a ⇝ d, P2 : d ⇝ a. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Case 1.2.1 and C (1) , C (2). The odd-chromatic color pattern on abcdef a can be arbitrary. Case 1.2.2. If {u, v} ∩ {a, d} ̸= ∅, then we assume without loss of generality that u = a and v ∈ P1. Write P1 = avP′ 1d, P′ 1 : v ⇝ d. As in Case 1.2.1, by Proposition 3.1 we may assume that {vc, ve} has the same color parity as {dc, de}. Now in G there are two Hamilton cycles given by C (1) = vP′ 1dP2abQ1feQ2cv, C… view at source ↗
Figure 4
Figure 4. Figure 4: Case 1.2.2 and C (1) , C (2). The odd-chromatic color pattern on abcdef a can be arbitrary. Case 1.3. Exactly half of the vertices in G′ have degree n ′/2. If there is a Hamilton {a, d}-path in G′ , then the proof follows as in Case 1.1. Otherwise, let u, v ∈ V (G′ ) have degree n ′/2 in G′ , then by Lemma 3.5 there is a Hamilton {u, v}-path P in G′ . As in Case 1.2, we have {b, c, e, f} ⊆ NG(u) ∩ NG(v), a… view at source ↗
Figure 5
Figure 5. Figure 5: Updating the collections C and P. Step 2: Extending the collection P by cherries, 2-matchings and singletons We order the colors in U and examine them one by one. For each c ∈ U, if some z1, z2, z3 ∈ R form a monochromatic cherry with color c, then we add that cherry to P, remove the vertices z1, z2, z3 from R and remove c from U. Otherwise, if some z1, z2, z3, z4 ∈ R form a monochromatic 2-matching with c… view at source ↗
Figure 6
Figure 6. Figure 6: The modification of P. Step 3: Merging paths in P using edges between endpoints We first merge some of the paths G1, . . . , Gm using only edges between their endpoints. In the beginning, let the set of endpoints of these paths be E = {u1, v1, . . . , um, vm}. Now we do the following. (i) If there exist w1, w2 ∈ E and distinct Fi1 , Fi2 ∈ P such that w1 is an endpoint of Fi1 , w2 is an endpoint of Fi2 , an… view at source ↗
Figure 7
Figure 7. Figure 7: Merging paths in P using cherries centered in R. Step 5: Close up the Hamilton cycle Now it remains to find a {z1, z2}-path P and a {z ′ 1 , z′ 2 }-path Q in the subgraph induced by R \ C, P and Q being disjoint, covering R \ C and avoiding colors in U, because then the required Hamilton cycle is given by z1w1F ′ 1w ′ 1 z ′ 1Qz′ 2w ′ 2F ′ 2w2z2P z1. To do this, consider two additional vertices z ∗ 1 , z∗ 2… view at source ↗
read the original abstract

The odd-Ramsey number $r_{\text{odd}}(n,H)$ of a graph $H$ is the minimum number of colors needed to edge-color $K_n$ so that in every copy of $H$ some color occurs an odd number of times, and the unique-Ramsey number $r_{\text{u}}(n,H)$ is the corresponding notion in which some color is required to occur not only an odd number of times but exactly once. In this paper, we address three questions from previous papers. We show $r_{\text{odd}}(n,K_{s,t})> n^{1/\left(\frac s2+\frac 1{2\lfloor t/8 \rfloor}\right)}$ when $s\leq t$ and $s$ is odd and $t$ is even, which is log-asymptotically tight when $s$ is fixed and $t\to\infty$. Next, we consider the odd-Ramsey number when the host graph to be edge-colored is a super-Dirac graph, and show that in any host graph with minimum degree at least $n/2+2$, the odd-Ramsey number of Hamilton cycles is non-trivial. Finally, we show that $r_\text{u}(n,C_n)> n/4$, which leads to a polynomial gap between $r_\text{odd}(n,C_n)$ and $r_\text{u}(n,C_n)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper establishes three results on variants of Ramsey numbers. It proves the lower bound r_odd(n, K_{s,t}) > n^{1/(s/2 + 1/(2⌊t/8⌋))} for s ≤ t with s odd and t even, which is log-asymptotically tight for fixed s and t → ∞. It shows that the odd-Ramsey number of Hamilton cycles is non-trivial in any host graph with minimum degree at least n/2 + 2. It also proves r_u(n, C_n) > n/4, yielding a polynomial gap between r_odd(n, C_n) and r_u(n, C_n).

Significance. If the constructions hold, the work advances the theory of odd- and unique-Ramsey numbers by supplying explicit combinatorial constructions that achieve new asymptotic lower bounds and separations. The log-asymptotic tightness for the bipartite case (fixed s, t → ∞) and the explicit polynomial gap for cycles are concrete strengths that improve on prior bounds.

minor comments (3)
  1. [Abstract] The exponent in the first abstract claim would be clearer if written with explicit parentheses around the denominator.
  2. [Introduction] The introduction should include a brief comparison table or paragraph contrasting the new bounds with the best previous results from the cited papers.
  3. [Section on Hamilton cycles] Notation for the super-Dirac threshold (minimum degree n/2 + 2) is used consistently but could be defined once in a preliminary section before the Hamilton-cycle result.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our results and for recommending minor revision. We appreciate the recognition that the log-asymptotic tightness for the bipartite case and the polynomial gap for cycles are concrete strengths.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes new lower bounds on odd-Ramsey and unique-Ramsey numbers via explicit combinatorial constructions (e.g., the exponent involving ⌊t/8⌋ arises from a counting argument on the given host graphs, the n/4 bound for r_u(n,C_n) from a cycle-avoiding edge-coloring, and the super-Dirac result from degree-threshold arguments). These derivations are self-contained, rely on new arguments rather than parameter-fitting, self-definitional reductions, or load-bearing self-citations, and remain independent of the target quantities by construction under the stated parity and minimum-degree hypotheses.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions of edge-colorings, subgraph copies, and minimum-degree conditions from graph theory; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Standard definitions and basic properties of graphs, edge colorings, and induced copies of subgraphs
    The paper operates entirely within the established framework of Ramsey theory and extremal graph theory.

pith-pipeline@v0.9.0 · 5561 in / 1238 out tokens · 46459 ms · 2026-05-11T01:07:13.407099+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Graph-codes.European Journal of Combinatorics, 116:103880, 2024

    Noga Alon. Graph-codes.European Journal of Combinatorics, 116:103880, 2024

    work page 2024

  2. [2]

    On generalized Ramsey theory: the bipartite case.Journal of Combinatorial Theory, Series B, 79(1):66–86, 2000

    Maria Axenovich, Zolt´ an F¨ uredi, and Dhruv Mubayi. On generalized Ramsey theory: the bipartite case.Journal of Combinatorial Theory, Series B, 79(1):66–86, 2000

    work page 2000

  3. [3]

    Upper bounds for multicolour Ramsey numbers.Journal of the American Mathematical Society, 2026

    Paul Balister, B´ ela Bollob´ as, Marcelo Campos, Simon Griffiths, Eoin Hurley, Robert Morris, Julian Sahasrabudhe, and Marius Tiba. Upper bounds for multicolour Ramsey numbers.Journal of the American Mathematical Society, 2026

    work page 2026

  4. [4]

    The generalized Ramsey number f(n, 5, 8) = 6 7 n+o(n).arXiv preprint arXiv:2408.01535, 2024

    Patrick Bennett, Ryan Cushman, and Andrzej Dudek. The generalized Ramsey number f(n, 5, 8) = 6 7 n+o(n).arXiv preprint arXiv:2408.01535, 2024

    work page arXiv 2024

  5. [5]

    The Erd˝ os-Gy´ arf´ as function f(n,4,5) = 5 6 n+o(n) – so Gy´ arf´ as was right.arXiv preprint arXiv:2207.02920, 2022

    Patrick Bennett, Ryan Cushman, Andrzej Dudek, and Pawe l Pra lat. The Erd˝ os-Gy´ arf´ as function f(n,4,5) = 5 6 n+o(n) – so Gy´ arf´ as was right.arXiv preprint arXiv:2207.02920, 2022

    work page arXiv 2022

  6. [6]

    Edge-coloring a graph G so that every copy of a graphHhas an odd color class.arXiv preprint arXiv:2307.01314, 2023

    Patrick Bennett, Emily Heath, and Shira Zerbib. Edge-coloring a graph G so that every copy of a graphHhas an odd color class.arXiv preprint arXiv:2307.01314, 2023

    work page arXiv 2023

  7. [7]

    Odd-Ramsey numbers of Hamilton cycles.arXiv preprint arXiv:2511.10497, 2025

    Simona Boyadzhiyska, Shagnik Das, Thomas Lesgourgues, and Kalina Petrova. Odd-Ramsey numbers of Hamilton cycles.arXiv preprint arXiv:2511.10497, 2025

    work page arXiv 2025

  8. [8]

    Odd-Ramsey numbers of complete bipartite graphs.European Journal of Combinatorics, 131:104235, 2026

    Simona Boyadzhiyska, Shagnik Das, Thomas Lesgourgues, and Kalina Petrova. Odd-Ramsey numbers of complete bipartite graphs.European Journal of Combinatorics, 131:104235, 2026

    work page 2026

  9. [9]

    New upper bounds for the Erd˝ os–Gy´ arf´ as problem on generalized Ramsey numbers.Combinatorics, Probability and Computing, 32(2):349–362, 2023

    Alex Cameron and Emily Heath. New upper bounds for the Erd˝ os–Gy´ arf´ as problem on generalized Ramsey numbers.Combinatorics, Probability and Computing, 32(2):349–362, 2023

    work page 2023

  10. [10]

    Campos, S

    Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe. An exponential improve- ment for diagonal Ramsey.arXiv preprint arXiv:2303.09521, 2023

    work page arXiv 2023

  11. [11]

    The Erd˝ os–Gy´ arf´ as problem on generalized Ramsey numbers.Proceedings of the London Mathematical Society, 110(1):1–18, 2015

    David Conlon, Jacob Fox, Choongbum Lee, and Benny Sudakov. The Erd˝ os–Gy´ arf´ as problem on generalized Ramsey numbers.Proceedings of the London Mathematical Society, 110(1):1–18, 2015

    work page 2015

  12. [12]

    Odd Ramsey numbers of multipartite graphs and hypergraphs.arXiv preprint arXiv:2507.19456, 2025

    Nicholas Crawford, Emily Heath, Owen Henderschedt, Coy Schwieder, and Shira Zerbib. Odd Ramsey numbers of multipartite graphs and hypergraphs.arXiv preprint arXiv:2507.19456, 2025

    work page arXiv 2025

  13. [13]

    Note – edge-coloring cliques with many colors on subcliques

    Dennis Eichhorn and Dhruv Mubayi. Note – edge-coloring cliques with many colors on subcliques. Combinatorica, 20(3):441–444, 2000

    work page 2000

  14. [14]

    Some remarks on the theory of graphs.Bulletin of the American Mathematical Society, 53:292–294, 1947

    Paul Erd˝ os. Some remarks on the theory of graphs.Bulletin of the American Mathematical Society, 53:292–294, 1947

    work page 1947

  15. [15]

    A variant of the classical Ramsey problem.Combinatorica, 17:459–467, 1997

    Paul Erd˝ os and Andr´ as Gy´ arf´ as. A variant of the classical Ramsey problem.Combinatorica, 17:459–467, 1997. 21

    work page 1997

  16. [16]

    A combinatorial problem in geometry.Compositio mathematica, 2:463–470, 1935

    Paul Erd˝ os and George Szekeres. A combinatorial problem in geometry.Compositio mathematica, 2:463–470, 1935

    work page 1935

  17. [17]

    Ramsey-type problem for an almost monochromatic K4.SIAM Journal on Discrete Mathematics, 23(1):155–162, 2009

    Jacob Fox and Benny Sudakov. Ramsey-type problem for an almost monochromatic K4.SIAM Journal on Discrete Mathematics, 23(1):155–162, 2009

    work page 2009

  18. [18]

    A new variant of the Erd˝ os–Gy´ arf´ as problem onK5

    Gennian Ge, Zixiang Xu, and Yixuan Zhang. A new variant of the Erd˝ os–Gy´ arf´ as problem onK5. arXiv e-prints, pages arXiv–2306, 2023

    work page 2023

  19. [19]

    Gupta, N

    Parth Gupta, Ndiame Ndiaye, Sergey Norin, and Louis Wei. Optimizing the CGMS upper bound on Rmsey numbers.arXiv preprint arXiv:2407.19026, 2024

    work page arXiv 2024

  20. [20]

    The asymptotics of r(4, t).Annals of Mathematics, 199(2):919– 941, 2024

    Sam Mattheus and Jacques Verstraete. The asymptotics of r(4, t).Annals of Mathematics, 199(2):919– 941, 2024

    work page 2024

  21. [21]

    Edge-coloring cliques with three colors on all 4-cliques.Combinatorica, 18(2):293–296, 1998

    Dhruv Mubayi. Edge-coloring cliques with three colors on all 4-cliques.Combinatorica, 18(2):293–296, 1998

    work page 1998

  22. [22]

    Parity check matrices and product representations of squares

    Assaf Naor and Jacques Verstraete. Parity check matrices and product representations of squares. Combinatorica, 28(2):163–185, 2008

    work page 2008

  23. [23]

    Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency

    C St JA Nash-Williams. Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency. InStudies in pure mathematics (presented to Richard Rado), pages 157–183. Academic Press London, 1971

    work page 1971

  24. [24]

    Hamilton connected graphs.Journal de Math´ ematiques Pures et Appliqu´ ees, 42(2127), 1963

    Oystein Ore. Hamilton connected graphs.Journal de Math´ ematiques Pures et Appliqu´ ees, 42(2127), 1963

    work page 1963

  25. [25]

    On the number of Hamiltonian cycles in Dirac graphs.Discrete Mathematics, 265(1-3):237–250, 2003

    G´ abor N S´ ark¨ ozy, Stanley M Selkow, and Endre Szemer´ edi. On the number of Hamiltonian cycles in Dirac graphs.Discrete Mathematics, 265(1-3):237–250, 2003

    work page 2003

  26. [26]

    Upper bounds for linear graph codes.Random Structures & Algorithms, 66(1):e21263, 2025

    Leo Versteegen. Upper bounds for linear graph codes.Random Structures & Algorithms, 66(1):e21263, 2025

    work page 2025

  27. [27]

    A variant of the Erd˝ os–Gy´ arf´ as problem forK8.European Journal of Combinatorics, 132:104267, 2026

    Fredy Yip. A variant of the Erd˝ os–Gy´ arf´ as problem forK8.European Journal of Combinatorics, 132:104267, 2026. 22

    work page 2026