Pith. sign in

REVIEW 1 major objections 5 minor 15 references

On the maximal anti-Ramsey problem of Burr, Erd\H{o}s, Graham, and S\'{o}s for $P_4$

T0 review · 1 major / 5 minor · reviewed 2026-07-08 · glm-5.2

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

Pith's one-line read Quadratic lower bound settles anti-Ramsey problem for P₄ at ε ≥ 1/2

desk verdict Resolves the ε ≥ 1/2 regime of the 1989 Burr–Erdős–Graham–Sós problem for P₄; proof has a fixable notational error in Lemma 1(ii) but the result stands. read the letter →

arxiv 2607.05896 v1 pith:TX57Q27B submitted 2026-07-07 math.CO

Zixuan Yang This is my paper · ORCID
classification math.CO
keywords epsilonchisproblemthereanti-ramseybinomburrexists
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 resolves the positive half of a 1989 problem of Burr, Erdős, Graham, and Sós about the maximal anti-Ramsey function χ_S(n, e, P₄), which measures the minimum number of colors needed to edge-color an n-vertex graph with at least e edges so that every copy of the 4-vertex path P₄ is rainbow (all edges distinct colors). When the graph is nearly complete — missing only ⌊n^{2−ε}⌋ edges — the question is whether the number of required colors must grow quadratically in n. Li, Ning, and Xie recently showed the answer is no for ε < 1/2. This paper proves the complementary result: for every ε ≥ 1/2, the number of required colors exceeds n²/72 for all sufficiently large n. The proof works by passing to the complement graph H (the missing edges), showing that when |E(H)| ≤ n^{3/2} one can find a large induced subgraph F of G with more than n²/4 edges, and that every rainbow-P₄ coloring of G forces the color classes restricted to F to be induced matchings. A double-counting argument combined with a Cauchy–Schwarz step then forces the number of such induced matchings — and hence the number of colors — above n²/72.

What carries the argument

The central objects are induced matchings — sets of edges no two of which share a vertex and between which no other graph edge connects. The proof establishes that rainbow-P₄ colorings force color classes on a dense subgraph to be induced matchings (Claims 2–3), then uses a double-counting identity relating the number q of induced matchings to the sum of squared matching sizes, bounded above via degree constraints from the complement graph, and bounded below via Cauchy–Schwarz applied to the total edge count of the subgraph.

What would settle it

A construction showing that for some ε ≥ 1/2, one can rainbow-P₄-color a nearly complete graph with o(n²) colors, or an error in the claim that color classes on F must be induced matchings (Claims 2–3), which is the structural step from which the counting argument derives.

Watch

Extended reading notes

Core claim

The threshold ε = 1/2 is the exact boundary for the maximal anti-Ramsey problem for P₄: below it, quadratic lower bounds fail (by prior work of Li–Ning–Xie); at or above it, any rainbow-P₄ coloring of a nearly complete graph requires Ω(n²) colors. The key mechanism is that when the complement has at most n^{3/2} edges, the color classes on a dense subgraph are forced to be induced matchings, and a counting argument shows there must be at least n²/72 of them.

Load-bearing premise

The argument depends on the specific constant 8 in the degree threshold for the vertex set B, and the bound n²/72 emerges from a chain of inequalities that are tight at the ε = 1/2 boundary; any slack in the intermediate degree bounds or edge-count estimates could change the constant, though not the qualitative quadratic growth.

Editorial extensions

If this is right

  • The 1989 problem of Burr, Erdős, Graham, and Sós is now fully resolved for P₄: the answer is positive if and only if ε ≥ 1/2, with the negative regime settled by Li–Ning–Xie and the positive regime settled here.
  • The constant 1/72 is unlikely to be tight; determining the correct quadratic constant c(ε) remains open.
  • The technique of reducing rainbow-P₄ colorings to induced-matching decompositions of a dense subgraph may extend to other bipartite host graphs L beyond P₄, particularly those whose rainbow colorings also force induced-matching structure.
  • The sharpness of the ε = 1/2 threshold — where |E(H)| ≤ n^{3/2} becomes available — suggests a phase transition in the combinatorial structure of nearly complete graphs at this complement-density boundary.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 5 minor

Summary. The paper addresses the maximal anti-Ramsey problem of Burr, Erdős, Graham, and Sós for $P_4$. The central result, Theorem 1, establishes that for every fixed $ε ≥ 1/2$ and sufficiently large $n$, $χ_S(n, C(n,2) − ⌊n^{2−ε}⌋, P_4) > n²/72$. This complements the recent negative result of Li–Ning–Xie for $0 < ε < 1/2$, thereby settling the threshold for the problem at $ε = 1/2$. The proof proceeds via Lemma 1, which shows that under the complement sparsity condition $|E(H)| ≤ n^{3/2}$, the edge set of a dense subgraph $F = G[U]$ cannot be partitioned into fewer than $n²/72$ induced matchings, combined with the observation (Claims 2–3) that rainbow-$P_4$ colorings yield induced matching color classes on $F$.

Significance. The result cleanly resolves the complementary regime to Li–Ning–Xie, identifying $ε = 1/2$ as the sharp threshold for the Burr–Erdős–Graham–Sós problem for $P_4$. The proof is short, self-contained, and parameter-free: the constant $1/72$ emerges from Cauchy–Schwarz and the intermediate bounds rather than from any fitted parameter. The structural argument reducing rainbow-$P_4$ colorings to induced matching decompositions is standard but effective. The paper would benefit from addressing the notational issue described below.

major comments (1)
  1. Lemma 1(ii), Claim 4 and Eqs. (4)–(6): There is a notational inconsistency that, taken literally, makes the proof incorrect. In the lemma statement, $F$ is defined as $G[U]$. However, in Eq. (4), the manuscript writes 'Since $F = H[U]$,' which contradicts the definition $F = G[U]$. This matters for the degree bound: $d_{G[U]}(v)$ can be as large as $|U|-1 ≈ 3n/4$, so $Σ C(d_F(v), 2)$ for $F = G[U]$ would be $Θ(n³)$, not $8n²$. The fix is straightforward: throughout Eqs. (4)–(6), $d_F(v)$ should be replaced by $d_{H[U]}(v)$. Since $v ∈ U$ implies $d_{H[U]}(v) ≤ d_H(v) ≤ 8√n$ and $Σ_{v∈U} d_{H[U]}(v) = 2|E(H[U])| ≤ 2|E(H)| ≤ 2n^{3/2}$, the bound $Σ C(d_{H[U]}(v), 2) ≤ 8n²$ holds and the final result $q > n²/72$ is unchanged. Additionally, in Claim 4, the assertion that endpoints $x, y$ of $e$ belong to $N_F(v)$ should read $N_{H[U]}(v)$: since $M_i$ is an induced matching in $F = G[U]$, no
minor comments (5)
  1. The abstract states 'there is an absolute constant $c > 0$' while Theorem 1 gives the explicit constant $c = 1/72$. Consider stating the explicit constant in the abstract for precision.
  2. In the proof of Claim 2, the inequality $n − 1 − 8√n > 2$ holds for $n ≥ 36$; specifying this threshold (or simply noting it holds for large $n$) would improve clarity.
  3. Eq. (5): the identity $Σ_{v∈U} d_F(v) = 2|E(H[U])|$ is correct only after replacing $d_F$ with $d_{H[U]}$; as written with $F = G[U]$, the left side equals $2|E(F)| = 2|E(G[U])|$, which is inconsistent.
  4. The reference to 'Ruzsa–Szemerédi graphs' in the introduction could cite the original source for completeness.
  5. Minor typographical issues: the abstract uses $χS$ without consistent subscript formatting; 'Erd˝ os' and 'S´ os' appear with encoding artifacts throughout.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a notational inconsistency in the proof of Lemma 1(ii). The referee is correct that Eqs. (4)–(6) and Claim 4 contain a typo: the degree bounds should be stated in terms of d_{H[U]}(v) rather than d_F(v), since F = G[U] and the relevant sparsity comes from the complement H. We will fix this in the revision. The mathematical argument and the final bound q > n²/72 are unaffected.

read point-by-point responses

  1. Referee: Lemma 1(ii), Claim 4 and Eqs. (4)–(6): There is a notational inconsistency. In the lemma statement, F is defined as G[U], but Eq. (4) writes 'Since F = H[U],' which contradicts the definition F = G[U]. The degree d_{G[U]}(v) can be as large as |U|-1 ≈ 3n/4, so Σ C(d_F(v), 2) for F = G[U] would be Θ(n³), not 8n². The fix: throughout Eqs. (4)–(6), d_F(v) should be replaced by d_{H[U]}(v). Since v ∈ U implies d_{H[U]}(v) ≤ d_H(v) ≤ 8√n and Σ_{v∈U} d_{H[U]}(v) = 2|E(H[U])| ≤ 2|E(H)| ≤ 2n^{3/2}, the bound Σ C(d_{H[U]}(v), 2) ≤ 8n² holds and q > n²/72 is unchanged. Additionally, in Claim 4, the assertion that endpoints x, y of e belong to N_F(v) should read N_{H[U]}(v).

    Authors: The referee is entirely correct, and we are grateful for this careful observation. There is a notational error in Eqs. (4)–(6) and Claim 4. In the lemma statement, F is defined as F = G[U], and this definition is used correctly throughout Claims 1–3 and the statement of part (ii). However, in Eq. (4), the manuscript incorrectly writes 'Since F = H[U],' which contradicts the definition. The intended meaning is that the complement of F is H[U], i.e., H[U] = G[U] = F. The degree bound in Eqs. (4)–(6) should be stated in terms of d_{H[U]}(v), not d_F(v). As the referee notes, d_F(v) = d_{G[U]}(v) can be as large as |U| - 1 ≈ 3n/4, which would make Σ C(d_F(v), 2) = Θ(n³), invalidating the bound 8n². The correct chain of reasoning is: since v ∈ U, we have d_{H[U]}(v) ≤ d_H(v) ≤ 8√n, and Σ_{v∈U} d_{H[U]}(v) = 2|E(H[U])| ≤ 2|E(H)| ≤ 2n^{3/2}. These yield Σ_{v∈U} C(d_{H[U]}(v), 2) ≤ 8n² as written. Similarly, in Claim 4, the assertion that the endpoints x, y of e belong to N_F(v) should read N_{H[U]}(v): since M_i is an induced matching in F = G[U], the absence of edges of F (i.e., G[U]) joining endpoints of f and e means that in the complement H[U], both x and y are neighbors of v. We will replace all occurrences of d_F(v) with d_{H[U]}(v) in Eqs. (4)–(6), correct the statement 'Since F = H[U]' to 'Since the complement of F is H[U],' and replace N_F(v) with N_{H[U]}(v) in Claim 4. The constant 1/72 and all other steps of the proof are unchanged. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is self-contained and parameter-free, with no self-citation chain or fitted-input-as-prediction.

full rationale

The paper proves Theorem 1 (a quadratic lower bound on χ_S(n, C(n,2) − ⌊n^{2−ε}⌋, P_4) for ε ≥ 1/2) via Lemma 1, which is entirely self-contained. The derivation chain is: (1) the complement H = Ḡ satisfies |E(H)| ≤ n^{3/2} because ε ≥ 1/2 forces 2−ε ≤ 3/2 — this is a direct consequence of the problem's edge count, not a fitted parameter; (2) the vertex partition B = {v : d_H(v) > 8√n}, U = V(G)∖B with |B| < n/4 follows from the degree-sum bound Σ d_H(v) = 2|E(H)| ≤ 2n^{3/2}; (3) |E(F)| > n²/4 follows from |U| > 3n/4 and |E(H)| ≤ n^{3/2}; (4) the constant 1/72 emerges from Cauchy–Schwarz applied to m = Σ|M_i| > n²/4 and Σ|M_i|² < 9n²/2, giving q ≥ m²/(Σ|M_i|²) > (n²/4)²/(9n²/2) = n²/72. No parameter is fitted to data and then presented as a prediction. The threshold ε = 1/2 is forced by the condition |E(H)| ≤ n^{3/2}, which is the natural boundary from the problem statement (the complement has ⌊n^{2−ε}⌋ edges). The only cited result that sets up the problem context is Li–Ning–Xie [7], which provides the negative answer for ε < 1/2; this is an independent external result by different authors, not a self-citation. The proof of Lemma 1 uses only standard inequalities (Cauchy–Schwarz, degree-sum) and the structural fact that color classes on F are induced matchings (Claims 2–3), which is proved from the rainbow-P_4 hypothesis. There is no step where an output is defined in terms of itself, no fitted input renamed as prediction, and no load-bearing self-citation chain. The skeptic's concern about F = G[U] versus H[U] in equations (4)–(6) is a correctness issue (a possible notational error in the proof), not a circularity issue — the bound itself is not constructed to equal its input by definition.

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

The proof introduces no free parameters (the constant 1/72 is derived, not fitted), no new axioms beyond standard mathematics, and no invented entities. The threshold ε = 1/2 is determined by the problem structure, not introduced ad hoc.

assumptions (3)
  • standard math Cauchy–Schwarz inequality: (Σ m_i)² ≤ q · Σ m_i²
    Used in equation (8) to lower-bound q in terms of m and Σ m_i². Standard mathematical tool.
  • domain assumption If every copy of P_4 in G is rainbow, then color classes on F form induced matchings
    Proved in Claims 2–3 of Lemma 1. This is the structural bridge from the anti-Ramsey coloring condition to the induced-matching partition problem.
  • standard math For ε ≥ 1/2, ⌊n^{2−ε}⌋ ≤ n^{3/2}
    Used in the proof of Theorem 1 to ensure |E(H)| ≤ n^{3/2}, enabling Lemma 1. This is a basic inequality.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the maximal anti-Ramsey problem of Burr, Erd\H{o}s, Graham, and S\'{o}s for $P_4$." pith.science (2026). https://pith.science/paper/TX57Q27B

@misc{pith2026260705896,
  author       = {Pith},
  title        = {Pith review of: On the maximal anti-Ramsey problem of Burr, Erd\Hos, Graham, and S\'os for $P_4$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TX57Q27B}},
  note         = {Machine review of arXiv:2607.05896}
}
abstract

Given a graph $L$, the maximal anti-Ramsey function $\chiS(n,e,L)$ denotes the minimum integer $\chiS$ for which there exists an $n$-vertex graph $G$ with at least $e$ edges admitting an edge-coloring with $\chiS$ colors in which each copy of $L$ in $G$ is rainbow. In 1989, Burr, Erd\H{o}s, Graham, and S\'{o}s posed the following problem: Is it true that for all $\epsilon>0$, there exists $c(\epsilon)>0$ such that for all sufficiently large $n$, $ \chiS\left(n,\binom{n}{2}-\lfloor n^{2-\epsilon}\rfloor,P_4\right)>c(\epsilon)n^2. $ Very recently, Li, Ning, and Xie gave a negative answer to the problem for all $0< \epsilon< 1/2$. In this note, we establish that a quadratic lower bound holds in the complementary regime $ \epsilon\geq 1/2$. More specifically, we prove that for all $\epsilon\ge 1/2$ and sufficiently large $n$, there is an absolute constant $c>0$ such that $ \chiS\left(n,\binom{n}{2}-\lfloor n^{2-\epsilon}\rfloor,P_4\right)>c n^2. $

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    N. Alon, A. Moitra, and B. Sudakov, Nearly complete graphs decomposable into large induced matchings and their applications, in Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19--22, 2012, 1079--1089

    work page 2012

  2. [2]

    N. Alon, A. Moitra, and B. Sudakov, Nearly complete graphs decomposable into large induced matchings and their applications, J. Eur. Math. Soc., 15 (2013), 1075--1096

    work page 2013

  3. [3]

    Buci\' c , K

    M. Buci\' c , K. Chen, and J. Ma, On a maximal anti-Ramsey conjecture of Burr, Erd o s, Graham, and S\' o s, arXiv:2603.18952, 2026

    work page arXiv 2026

  4. [4]

    S. A. Burr, P. Erd o s, P. Frankl, R. L. Graham, and V. T. S\' o s, Further results on maximal anti-ramsey graphs, in Graph Theory, Combinatorics, and Applications, Vol. I, Y. Alavi, A. Schwenk (Eds.), John Wiley and Sons, New York, 1988, 193--206

    work page 1988

  5. [5]

    S. A. Burr, P. Erd o s, R. L. Graham, and V. T. S\' o s, Maximal antiramsey graphs and the strong chromatic number, J. Graph Theory, 13 (1989), no. 3, 263--282

    work page 1989

  6. [6]

    Erd o s, On a theorem of Rademacher-Turán, Illinois J

    P. Erd o s, On a theorem of Rademacher-Turán, Illinois J. Math., 6 (1962), 122--127

    work page 1962

  7. [7]

    Erd o s, Problems and results in combinatorial analysis and combinatorial number theory, in Graph theory, combinatorics, and applications 1, Kalamazoo, MI, 1988, 397--406

    P. Erd o s, Problems and results in combinatorial analysis and combinatorial number theory, in Graph theory, combinatorics, and applications 1, Kalamazoo, MI, 1988, 397--406

    work page 1988

  8. [8]

    Erd o s, M

    P. Erd o s, M. Simonovits, and V. T. S\' o s, Anti-Ramsey theorems, in Infinite and finite sets (Colloq., Keszthely, 1973); dedicated to P. Erdős on his 60th birthday, Vol. II, Colloq. Math. Soc. J\' a nos Bolyai, Vol. 10, North Holland, Amsterdam, 633--643

    work page 1973

Show all 15 references
  1. [9]

    Erd o s and T

    P. Erd o s and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar., 10 (1959), 337--356

    1959

  2. [10]

    R. J. Faudree, R. H. Schelp, A. Gy\' a rf\' a s, and Zs. Tuza, The strong chromatic index of graphs, Ars Combin., 29 (1990), 205--211

    1990

  3. [11]

    Füredi and D

    Z. Füredi and D. S. Gunderson, Extremal numbers for odd cycles, Combin. Probab. Comput., 24 (2015), 641--645

    2015

  4. [12]

    J. Fox, H. Huang, and B. Sudakov, On graphs decomposable into induced matchings of linear sizes, Bull. Lond. Math. Soc., 49 (2017), no. 1, 45--57

    2017

  5. [13]

    M. Li, B. Ning, and T. Xie, Two problems of Burr, Erd o s, Graham, and S\' o s on maximal anti-Ramsey functions for P_4 , arXiv:2606.30505v1, 2026

    2026 arXiv

  6. [14]

    Lužar, E

    B. Lužar, E. M\' a čajov\' a , M. Škoviera, and R. Sot\' a k, Strong edge colorings of graphs and the covers of Kneser graphs, J. Graph Theory, 100 (2022), no. 4, 686--697

    2022

  7. [15]

    G. N. Sárközy and S. M. Selkow, On an anti-Ramsey problem of Burr, Erd o s, Graham, and T. S\' o s, J. Graph Theory, 52 (2006), no. 2, 147--156

    2006

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.