Edge-coloring $K_{n, n}$ with no 2-colored $C_{2k}$

Deepak Bal; Patrick Bennett

REVIEW 2 major objections 3 minor 24 references

Edge-coloring $K_{n, n}$ with no 2-colored $C_{2k}$

T0 review · 2 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that coloring the edges of $K_{n,n}$ so that no 6-cycle uses only two colors requires asymptotically $\frac{7}{20} n$ colors, and improves the bounds for all longer even cycles.

desk verdict Solid paper: settles the C6 asymptotic and improves bounds for all longer cycles; the p+q=k worry in the stress test is a red herring, not a real gap. read the letter →

arxiv 2507.13329 v1 pith:LSTOPFIN submitted 2025-07-17 math.CO

Deepak Bal , Patrick Bennett This is my paper

classification math.CO MSC 05C1505C5505C6505D40

keywords generalizedRamseynumberbipartitetheoryevencyclesconflict-freehypergraphmatchingsedge-coloringrandomsparsehypergraphsK_{nn}

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies the generalized Ramsey number $r(K_{n,n}, C_{2k}, 3)$, the minimum number of colors needed to color the edges of the complete bipartite graph $K_{n,n}$ so that every copy of the even cycle $C_{2k}$ uses at least three colors. It establishes that for $k=3$ this number is asymptotically $\frac{7}{20} n$, and for every $k \ge 4$ it lies between an explicit lower bound and the upper bound $\frac{3k-2}{2(k-1)(2k-1)} n + o(n)$. The upper bound answers a question of Lane and Morrison about removing an integer-floor obstruction from the previously known bound. The interest is that the lower and upper arguments are different in character, yet for six-cycles they meet exactly in the limit.

What carries the argument

The upper-bound construction is carried by the conflict-free hypergraph matching theorem of Joos, Mubayi and Smith (Theorem 3.1), which produces a matching in a hypergraph $\mathcal{H} = \mathcal{H}_1 \cup \mathcal{H}_2$ that covers all of $P$ and avoids forbidden submatchings called conflicts. The paper builds $\mathcal{H}_1$ whose edges are colored bicliques $K_{k-1,2k-1}$ with the $(k-1)$-vertex side belonging to a random sparse linear hypergraph $S_A$ or $S_B$, obtained by randomly retaining edges of an $(n,k-1,2)$-Steiner system; the $b$-side of each biclique is chosen so that its vertex pairs avoid the edges of $S_A \cup S_B$. A second hypergraph $\mathcal{H}_2$ consists of spare colored edges that handle leftover pairs. The conflict systems $\mathcal{C}$ and $\mathcal{D}$ encode all ways a two-colored $C_{2k}$ could form, and the forced overlap of the small sides is the innovation that makes the packing more efficient.

What would settle it

Check the parameter relation $p+q=k$ in Theorem 3.1 against the actual number of $P$ and $Q$ vertices in a generic $\mathcal{H}_1$ edge; if the relation cannot be met, the upper-bound proof does not go through. A complementary check is to verify the inequalities (H1)--(H4), (C1)--(C3), and (D1)--(D4) numerically for a fixed small $k$, such as $k=4$, using $d$ as defined in equation (12).

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.1: for every $k \ge 4$, $$\frac{4\sqrt{$k^{4}$-$6k^{3}$+$12k^{2}$-9k+2}-$4k^{2}$+12k-5}{2(k-2)} n \le r(K_{n,n}, C_{2k}, 3) \le \frac{3k-2}{2(k-1)(2k-1)} n + o(n),$$ and for $k=3$, $$r(K_{n,n}, C_6, 3) = \frac{7}{20} n + o(n).$$ The $k=3$ statement is an asymptotically sharp estimate, and the upper bound improves the earlier bound by a constant factor for large $k$, resolving the Lane--Morrison question. The insight behind the improvement is that colored bicliques $K_{k-1,2k-1}$ can be packed much more efficiently if their small sides are forced to lie inside a sparse linear hypergraph; two such bicliques may overlap without creating a two-colored $C_{2k}$, so fewer colors are needed.

Load-bearing premise

The upper bound stands or falls with the black-box conflict-free matching theorem: if the hypergraph the paper constructs does not satisfy every one of its quantitative hypotheses, there is no guarantee that the required conflict-free perfect matching, and hence the coloring, exists.

Editorial extensions

If this is right

For $k=3$, any valid coloring needs at least $\frac{7}{20} n - o(n)$ colors and one exists with at most $\frac{7}{20} n + o(n)$ colors, so the asymptotic answer for six-cycles is now known exactly.
For every $k \ge 4$, the new bounds improve both the previous lower and upper bounds; for large $k$ the new upper bound is roughly $\frac{3}{4}$ of the old one.
The paper conjectures that the upper bound is tight for all $k$, and proves this conjecture under the additional assumption that every monochromatic component is essentially a biclique $K_{k-1,b}$ with $b \ge k$.
The upper-bound construction provides an explicit coloring scheme: most edges are covered by colored bicliques whose small sides lie in the sparse hypergraphs, and a tiny leftover set of edges is colored with extra colors.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper, the forced-overlap packing idea looks transferable: for any forbidden bipartite subgraph built from overlapping bicliques, confining the small sides of the bicliques to a sparse linear hypergraph could yield improved upper bounds.
The clean match at $k=3$ makes $k=4$ the natural next test of the conjecture; the new interval $[0.227n, 0.239n]$ is narrow enough that a sharper count on either side might close the gap.
A reader wanting to fully trust the upper bound should first reconcile the parameter relation $p+q=k$ in Theorem 3.1 with the $O(k^2)$ vertices from $P \cup Q$ appearing in each $\mathcal{H}_1$ edge; the paper does not spell this out, so this is an open technical point rather than an established failure.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this is a good paper. It answers Lane and Morrison's question, proves the first asymptotically sharp constant for C6, and improves both bounds for all k≥4. The k=3 lower bound is self-contained and clean; the upper bound is a careful application of the JMS conflict-free matching theorem with a genuine new idea: forcing the packed bicliques to share their (k−1)-sides, which is what buys the better constant. The paper deserves serious refereeing.

What is actually new: the packing trick is real and accounts for the improvement; the paper also removes the floor in the denominator that Lane and Morrison flagged. The lower bound argument, while elementary, is done with care, and the k=3 specialization via monotonicity of h(a) is a neat touch.

Soft spots: the stress-test concern about Theorem 3.1's p+q=k is not a real problem. The theorem's k is a dummy parameter: you instantiate it with the actual edge size in H1, which is Θ(k^2) here. The paper should have renamed it to avoid confusion, and the ε in (11) technically needs to be chosen with respect to that larger parameter, but that is a one-line fix. The initial size inequalities (d^ε ≤ |P|, |P∪Q| ≤ exp(d^{ε^3})) are clearly satisfiable for the stated d, though the paper does not spell them out. So the concern is expository, not structural. The dense asymptotic counts in Sections 3.3–3.5 are standard for this method; I found no circularity or fitted constants. The reliance on the external theorem from [16] is explicit and appropriate.

Who this is for: anyone working in generalized Ramsey theory or conflict-free hypergraph matchings. It is a solid application that extends the method, and the conjecture at the end is plausible. I would cite it.

Recommendation: send it to a good combinatorics journal; a serious referee will want the parameter renaming fixed and a bit more detail on the auxiliary hypotheses, but the main result is correct as far as I can see.

Referee Report

2 major / 3 minor

Summary. This paper studies the generalized Ramsey number r(K_{n,n}, C_{2k}, 3). It proves by a stripping argument a new lower bound for every k >= 4 and a sharp asymptotic value 7/20 n + o(n) for k = 3. For the upper bound it constructs a coloring via conflict-free hypergraph matchings, using as color classes appropriately packed bicliques K_{k-1,2k-1} with small sides in sparse linear hypergraphs S_A/S_B and large sides whose pairs avoid S_A/S_B; leftover edges are assigned fresh colors in a second stage. The conflict systems C and D are designed so that a C-union-D-free P-perfect matching corresponds to a coloring with no 2-colored C_{2k}.

Significance. If the proof is completed, the results are significant: they improve both known bounds for every k, give the first sharp asymptotic value for C_6, and answer a question of Lane and Morrison. The lower-bound argument is a clean self-contained weighting/stripping argument with explicit inequalities, and the upper-bound application of conflict-free matching is natural and technically detailed. The main issues are missing definitions and hypothesis checks rather than obvious mathematical errors.

major comments (2)

[Section 3.2.1 and Section 3.3] The set W of first-stage colors is never given a cardinality. The total number of colors in the construction is |W| + |W'|, so the upper bound in Theorem 1.1 can only be verified from the stated computations if |W| = (3k-2)/(2(k-1)(2k-1)) n (or an equivalent quantity of order n). The display for d_{H1}(e) currently reads as if |W| were part of the constant 3k-2 divided by (2k-1)!; this makes the color count unverifiable and, if |W| were constant, the construction would contradict the lower bound. Please define W explicitly, correct the display, and confirm that d has the form (12). This is load-bearing because the color count is the statement being proved.
[Section 3.1 and Section 3.2] The hypotheses of Theorem 3.1 are not explicitly checked in the setup. The constructed H1 has p=(k-1)(2k-1) P-vertices and q=(3k-2)+C(2k-1,2) Q-vertices per edge, so p+q=4k^2-3k, not the cycle parameter k appearing in the theorem's statement 'For p+q=k'. Since the theorem is being applied with a different value of its parameter (call it K=p+q), this renaming must be stated, and the size inequalities d^epsilon <= |P| <= |P union Q| <= exp(d^{epsilon^3}) should be verified for |P|=n^2, |P union Q|=Theta(n^2), and d=Theta(n^{2k-delta}) with epsilon sufficiently small. These are routine but currently omitted.

minor comments (3)

[Section 3.2.2, Claim 3.4] The assertion that if every c'-colored biclique shares two vertices with the single c-colored biclique then their small sides all coincide is not immediate; it uses linearity of S_A and S_B together with the condition (Z choose 2) subseteq E_A union E_B. Please add the one-sentence justification, since this is the step that prevents a two-biclique 2-colored cycle.
[Section 3.1] The parameter ell in Theorem 3.1 is not assigned in the application; one should take ell = 2k to match the bounds in (C1) and (D1).
[Section 2] In the text following the k=3 lower bound, the notation f(K_{n,n}, C_6, 3) is used instead of r(K_{n,n}, C_6, 3); please make the notation consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: both bounds are derived from explicit constructions or counting arguments, with no fitted input renamed as a prediction and no load-bearing self-citation.

full rationale

The paper's derivation chain is self-contained in the sense relevant to circularity. The lower bounds in Section 2 are proved from first principles: Claim 2.1, the stripping process, and the counting identities (4) and (5) lead to an explicit inequality involving the total number of colors g, and the constants in Theorem 1.1 come from minimizing an explicit function h(a). In particular, the k=3 value 7/20 is obtained by evaluating h(1/2), not by assuming the desired bound. The upper bound in Section 3 is also not circular: the construction defines H1, H2, C, and D explicitly, checks the degree and conflict conditions, and then invokes the external conflict-free matching theorem of Joos, Mubayi, and Smith [16] as a black box. The constants such as |W| = 3k-2 and the K_{k-1,2k-1} size are structural choices in the construction rather than parameters fitted to the final answer. The paper's self-citations to [3] and [5] are contextual and not load-bearing: the central upper-bound argument uses the external theorem [16], and the lower bound does not rely on prior results of the authors. Theorem 4.2, which proves a matching lower bound under extra structural assumptions, is explicitly labeled as motivation and is not used to derive the main theorem. The skeptic's concern about whether Theorem 3.1's hypothesis p+q=k matches the paper's H1 parameters is a correctness or hypothesis-checking issue, not a circularity issue: even if that concern were valid, it would not make any equation of the paper reduce to its own input by construction. No fitted parameter is renamed as a prediction, no known result is merely relabeled, and no uniqueness theorem is imported from the authors' own work. Therefore the circularity score is 0.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The final constants contain no data-fitted parameters. Auxiliary constants delta, epsilon, and kappa are chosen by hand to satisfy inequalities and do not enter the answer. The proof leans on Wilson's Steiner-system existence theorem, McDiarmid's inequality, and the external conflict-free matching theorem of Joos, Mubayi and Smith.

free parameters (3)

delta
Small positive constant used in the random hypergraph SA and in all asymptotic estimates; must satisfy delta < 1/4 and delta << epsilon. It is chosen by hand and cancels from the final constants.
epsilon
Small positive constant in the conflict-free matching theorem; must satisfy delta << epsilon << 1/k. It is chosen by hand to make the degree and codegree inequalities hold.
kappa
Sufficiently large constant added to d in equation (12) to absorb lower-order error terms in the degree computations.

assumptions (5)

standard math Wilson's existence theorem for (n,k-1,2)-Steiner systems
Provides the complete linear hypergraph K from which SA is sampled in Lemma 3.2.
standard math McDiarmid's bounded differences inequality
Used to prove concentration for the random subgraph SA, giving properties (S1), (S2), and (S4).
standard math Joos-Mubayi-Smith conflict-free matching theorem (Theorem 3.1)
External black box producing the conflict-free P-perfect matching that encodes the coloring; the entire upper bound depends on it.
standard math Path containment: a graph of minimum degree at least k contains a path on 2k vertices
Used in Claim 2.1 of the lower bound to rule out monochromatic components with minimum degree k or more.
domain assumption Rounding n to an admissible integer for Wilson's design
Applied in the proof of Lemma 3.2; all asymptotic bounds are unaffected by rounding n to satisfy Wilson's divisibility conditions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Edge-coloring $K_{n, n}$ with no 2-colored $C_{2k}$." pith.science (2026). https://pith.science/paper/LSTOPFIN

@misc{pith2026250713329,
  author       = {Pith},
  title        = {Pith review of: Edge-coloring $K_n, n$ with no 2-colored $C_2k$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LSTOPFIN}},
  note         = {Machine review of arXiv:2507.13329}
}

abstract

The generalized Ramsey number $r(G, H, q)$ is the minimum number of colors needed to color the edges of $G$ such that every isomorphic copy of $H$ has at least $q$ colors. In this note, we improve the upper and lower bounds on $r(K_{n, n}, C_{2k}, 3)$. Our upper bound answers a question of Lane and Morrison. For $k=3$ we obtain the asymptotically sharp estimate $r(K_{n, n}, C_6, 3) = \frac{7}{20} n + o(n)$.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

24 extracted references · 21 canonical work pages

[16]

F. Joos, D. Mubayi, and Z. Smith. Conflict-free hypergraph matchings and coverings. arXiv preprint arXiv:2407.18144, 2024

arXiv 2024
[1]

Axenovich

M. Axenovich. A generalized Ramsey problem. Discrete Mathematics, 222(1-3):247–249, 2000

work page 2000
[2]

Axenovich, Z

M. Axenovich, Z. F¨ uredi, and D. Mubayi. On generalized Ramsey theory: the bipartite case.J. Combin. Theory Ser. B , 79(1):66–86, 2000

work page 2000
[3]

D. Bal, P. Bennett, E. Heath, and S. Zerbib. Generalized Ramsey numbers of cycles, paths, and hypergraphs. arXiv preprint arXiv:2405.15904 , 2024

work page Pith review arXiv 2024
[4]

Balogh, S

J. Balogh, S. English, E. Heath, and R. A. Krueger. Lower bounds on the Erd˝ os–Gy´ arf´ as problem via color energy graphs. Journal of Graph Theory , 103(2):378–409, 2023

work page 2023
[5]

Bennett, R

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

arXiv 2024
[6]

Bennett, R

P. Bennett, R. Cushman, A. Dudek, and P. Pra lat. The Erd˝ os-Gy´ arf´ as functionf (n, 4, 5) = 5 6 n + o(n)— so Gy´ arf´ as was right.J. Combin. Theory Ser. B , 169:253–297, 2024. 12

work page 2024
[7]

Cameron and E

A. Cameron and E. Heath. A (5 , 5)-colouring of Kn with few colours. Combinatorics, Probability and Computing, 27(6):892–912, 2018

work page 2018

Show all 24 references

[8]

Cameron and E

A. Cameron and E. 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

2023
[9]

Conlon, J

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

2015
[10]

Delcourt and L

M. Delcourt and L. Postle. Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings. arXiv preprint arXiv:2204.08981 , 2022

2022 arXiv
[11]

R. Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, sixth edition,
[12]

P. Erd˝ os. Problems and results on finite and infinite graphs. Recent Advances in Graph Theory (Proc. Second Czechoslovak Sympos., Prague, 1974) , pages 183–192, 1975

1974
[13]

Erd˝ os and A

P. Erd˝ os and A. Gy´ arf´ as. A variant of the classical Ramsey problem.Combinatorica, 17(4):459–467, 1997

1997
[14]

Glock, F

S. Glock, F. Joos, J. Kim, M. K¨ uhn, and L. Lichev. Conflict-free hypergraph matchings. Journal of the London Mathematical Society, 109(5):e12899, 2024

2024
[15]

Joos and D

F. Joos and D. Mubayi. Ramsey theory constructions from hypergraph matchings. Proceedings of the American Mathematical Society, 152(11):4537–4550, 2024

2024
[17]

Lane and N

A. Lane and N. Morrison. Generalized Ramsey Numbers via Conflict-Free Hypergraph Matchings. arXiv preprint arXiv:2405.16653, 2024

2024 arXiv
[18]

McDiarmid et al

C. McDiarmid et al. On the method of bounded differences. Surveys in combinatorics , 141(1):148–188, 1989

1989
[19]

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

1998
[20]

D. Mubayi. An explicit construction for a Ramsey problem. Combinatorica, 24(2):313–324, 2004

2004
[21]

Pippenger and J

N. Pippenger and J. Spencer. Asymptotic behavior of the chromatic index for hypergraphs. Journal of Combinatorial Theory, Series A , 51(1):24–42, May 1989

1989
[22]

R. M. Wilson. An existence theory for pairwise balanced designs, I: Composition theorems and mor- phisms. Journal of Combinatorial Theory, Series A , 13(2):220–245, 1972

1972
[23]

R. M. Wilson. An existence theory for pairwise balanced designs, II: The structure of PBD-closed sets and the existence conjectures. Journal of Combinatorial Theory, Series A , 13(2):246–273, 1972

1972
[24]

R. M. Wilson. An existence theory for pairwise balanced designs, III: Proof of the existence conjectures. Journal of Combinatorial Theory, Series A , 18:71–79, 1975. 13

1975

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [16]

F. Joos, D. Mubayi, and Z. Smith. Conflict-free hypergraph matchings and coverings. arXiv preprint arXiv:2407.18144, 2024

arXiv 2024

[2] [1]

Axenovich

M. Axenovich. A generalized Ramsey problem. Discrete Mathematics, 222(1-3):247–249, 2000

work page 2000

[3] [2]

Axenovich, Z

M. Axenovich, Z. F¨ uredi, and D. Mubayi. On generalized Ramsey theory: the bipartite case.J. Combin. Theory Ser. B , 79(1):66–86, 2000

work page 2000

[4] [3]

D. Bal, P. Bennett, E. Heath, and S. Zerbib. Generalized Ramsey numbers of cycles, paths, and hypergraphs. arXiv preprint arXiv:2405.15904 , 2024

work page Pith review arXiv 2024

[5] [4]

Balogh, S

J. Balogh, S. English, E. Heath, and R. A. Krueger. Lower bounds on the Erd˝ os–Gy´ arf´ as problem via color energy graphs. Journal of Graph Theory , 103(2):378–409, 2023

work page 2023

[6] [5]

Bennett, R

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

arXiv 2024

[7] [6]

Bennett, R

P. Bennett, R. Cushman, A. Dudek, and P. Pra lat. The Erd˝ os-Gy´ arf´ as functionf (n, 4, 5) = 5 6 n + o(n)— so Gy´ arf´ as was right.J. Combin. Theory Ser. B , 169:253–297, 2024. 12

work page 2024

[8] [7]

Cameron and E

A. Cameron and E. Heath. A (5 , 5)-colouring of Kn with few colours. Combinatorics, Probability and Computing, 27(6):892–912, 2018

work page 2018