Pith. sign in

REVIEW 1 major objections 2 minor 1 cited by

Two problems of Burr, Erd\H os, Graham, and S\'os on maximal anti-Ramsey functions for $P_4$

T0 review · 1 major / 2 minor · reviewed 2026-06-30 · grok-4.3

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

Pith's one-line read The number of colors needed to rainbow all P4 copies is at most linear in u for any graph with un edges, but at most n to a power below 2 when the graph misses n to the power 2-ε edges.

desk verdict Resolves the two 1989 Burr-Erdős-Graham-Sós problems with one yes and one no, but the linear upper bound rests on an application of the Lužar characterization whose fit to the odd Kneser graphs is not shown in the abstract. read the letter →

arxiv 2606.30505 v1 pith:YDALZYWG submitted 2026-06-29 math.CO

Mingze Li , Bo Ning , Tianying Xie This is my paper · ORCID
classification math.CO
keywords anti-RamseyfunctionsP4strongedge-coloringKnesergraphsgraphdensityedgecoloringsmaximal
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 two problems posed by Burr, Erdős, Graham, and Sós on the maximal anti-Ramsey function χ_S(n,e,P4), which is the smallest number of colors sufficient to edge-color any n-vertex graph with at least e edges so that every path of length three is rainbow. It establishes an affirmative answer to the first problem by proving a linear upper bound in the parameter u when e equals floor(un). It establishes a negative answer to the second problem by proving a subquadratic upper bound when e is the complete-graph edge count minus floor(n to the power 2-ε). A reader would care because the function tracks how edge density forces more colors to avoid non-rainbow P4 subgraphs, and the results separate the scaling at sparse versus dense regimes.

What carries the argument

Local density inequality applied to strong edge-colorings of odd Kneser graphs, combined with the Alon-Moitra-Sudakov dense-graph construction.

What would settle it

A family of graphs with floor(un) edges in which more than linear-in-u colors are required to make every P4 rainbow, or a proof that χ_S remains quadratic for every ε when only n to the power 2-ε edges are deleted from the complete graph.

Watch

Extended reading notes

Core claim

There exists C>0 such that χ_S(n, floor(un), P4) < C u for all u≥1 and all sufficiently large n. For every fixed 0<ε<1/2 there exist γ>0 and arbitrarily large n such that χ_S(n, binom(n,2)−floor(n^{2−ε}), P4) ≤ n^{2−γ}. The first bound is proved via a local density inequality together with strong edge-colorings of odd Kneser graphs; the second bound is proved via the Alon-Moitra-Sudakov construction.

Load-bearing premise

The known characterization of k-regular graphs whose strong chromatic index equals 2k-1 applies directly to the odd Kneser graphs that appear in the local-density argument, and the Alon-Moitra-Sudakov graphs meet the exact edge-count and P4-density requirements of the second claim.

Editorial extensions

If this is right

  • The linear upper bound holds uniformly for every u at least 1 once n is large enough.
  • The subquadratic upper bound holds for infinitely many n at every fixed ε in (0,1/2).
  • The function χ_S need not grow quadratically even when the host graph is missing only a polynomial number of edges.
  • The two regimes are separated by the choice of edge density in the definition of χ_S.

Reading between the lines

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

  • The same density-plus-coloring technique could be tested on anti-Ramsey functions for longer paths or other small graphs.
  • Scaling behavior at intermediate densities between linear and near-complete remains open and could be probed by varying the exponent in the missing-edge term.
  • Explicit small-n instances of the Kneser-based or Alon-Moitra-Sudakov constructions could be enumerated to estimate the hidden constants C and γ.
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 / 2 minor

Summary. The manuscript resolves two problems posed by Burr, Erdős, Graham, and Sós on the maximal anti-Ramsey function χ_S(n,e,P4). It affirms problem (i) by proving there exists C>0 such that χ_S(n,⌊un⌋,P4)<Cu for all u≥1 and all sufficiently large n, via a local-density inequality obtained from strong edge-colorings of odd Kneser graphs that invokes the Lužar-Máčajová-Škoviera-Soták characterization of k-regular graphs with strong chromatic index 2k−1. It gives a negative answer to problem (ii) by exhibiting, for every fixed 0<ε<1/2, a γ>0 and arbitrarily large n such that χ_S(n, binom(n,2)−⌊n^{2−ε}⌋,P4)≤n^{2−γ}=o(n²), using the Alon-Moitra-Sudakov construction.

Significance. If correct, the results settle both open problems: the first supplies the conjectured linear upper bound in the sparse regime, while the second disproves the conjectured quadratic lower bound in the dense regime. The paper explicitly credits the Lužar et al. characterization and the Alon-Moitra-Sudakov construction as the main tools, which is a strength when the applicability is verified.

major comments (1)
  1. [local-density argument / proof of the linear upper bound] Proof of the affirmative answer to (i) (local-density argument): the invocation of the Lužar-Máčajová-Škoviera-Soták theorem to conclude that the strong chromatic index of the odd Kneser graphs equals 2k−1 requires explicit verification that these graphs are k-regular and satisfy every additional hypothesis of the characterization (e.g., precise matching or neighborhood conditions). If any hypothesis fails for the specific Kneser graphs arising in the density estimate, the claimed linear bound χ_S(n,⌊un⌋,P4)<Cu cannot be derived.
minor comments (2)
  1. Ensure that the precise statement of the Lužar et al. theorem (including all hypotheses) is quoted or referenced with page numbers so that the reader can check applicability without consulting the external paper.
  2. In the statement of the negative result for (ii), clarify whether the Alon-Moitra-Sudakov graphs are shown to contain P4 copies under the exact edge-density hypothesis used in the definition of χ_S.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for identifying a point that improves the clarity of our local-density argument. We address the comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [local-density argument / proof of the linear upper bound] Proof of the affirmative answer to (i) (local-density argument): the invocation of the Lužar-Máčajová-Škoviera-Soták theorem to conclude that the strong chromatic index of the odd Kneser graphs equals 2k−1 requires explicit verification that these graphs are k-regular and satisfy every additional hypothesis of the characterization (e.g., precise matching or neighborhood conditions). If any hypothesis fails for the specific Kneser graphs arising in the density estimate, the claimed linear bound χ_S(n,⌊un⌋,P4)<Cu cannot be derived.

    Authors: We agree that an explicit verification is necessary for rigor. In the revised manuscript we will add a short subsection (or appendix paragraph) that directly confirms the odd Kneser graphs arising in the density estimate are k-regular and satisfy every hypothesis of the Lužar–Máčajová–Škoviera–Soták characterization, including the required matching and neighborhood conditions. With this verification in place the application of the theorem is justified and the linear upper bound follows as claimed. We thank the referee for prompting this clarification. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity detected; derivation relies on independent external theorems

full rationale

The paper affirms problem (i) via a local-density argument that invokes the Lužar-Máčajová-Škoviera-Soták characterization of k-regular graphs with strong chromatic index 2k−1, and affirms a negative answer to (ii) via the Alon-Moitra-Sudakov construction. Both cited results are by disjoint author sets, are stated independently of the present claims, and are not reduced to any fitted parameter or self-citation chain inside the paper. No step matches any of the enumerated circularity patterns; the central bounds are derived from these external inputs rather than being equivalent to them by construction.

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

Only abstract available; the paper invokes two external theorems whose status as standard domain assumptions cannot be audited here.

assumptions (2)
  • domain assumption Characterization of k-regular graphs with strong chromatic index exactly 2k-1 holds for the odd Kneser graphs used in the density argument.
    Invoked for the proof of the linear upper bound.
  • domain assumption Alon-Moitra-Sudakov graphs satisfy the exact edge-count and P4-density conditions needed for the o(n²) upper bound.
    Invoked for the negative answer to the second problem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Two problems of Burr, Erd\H os, Graham, and S\'os on maximal anti-Ramsey functions for $P_4$." pith.science (2026). https://pith.science/paper/YDALZYWG

@misc{pith2026260630505,
  author       = {Pith},
  title        = {Pith review of: Two problems of Burr, Erd\H os, Graham, and S\'os on maximal anti-Ramsey functions for $P_4$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YDALZYWG}},
  note         = {Machine review of arXiv:2606.30505}
}
abstract

Burr, Erd\H os, Graham, and S\'os introduced the maximal anti-Ramsey function $\chi_{\mathrm{S}}(n,e,L)$, the minimum number of colors required over all $n$-vertex graphs with at least $e$ edges such that every copy of $L$ is rainbow. In \cite{BEGS1989}, they posed the following two problems: (i) Is it true that there exists $C>0$, such that for all $u\ge 1$, $\chi_{\mathrm{S}}\left(n,\lfloor un \rfloor,P_4 \right)<Cu$ holds for all sufficiently large $n$? (ii) Is it true that for all $\epsilon >0$, there exists $c(\epsilon)>0$ such that for all sufficiently large $n$, \\ $\chi_{\mathrm{S}}\left(n,\binom{n}{2}-\lfloor n^{2-\epsilon} \rfloor,P_4 \right)>c(\epsilon)n^{2}$? In this note, we give an affirmative answer to the first problem and a negative answer to the second problem. For the first problem, our proof uses a local density inequality with strong edge-colorings of odd Kneser graphs. In particular, our proof uses the characterization by Lu\v{z}ar, M\'{a}\v{c}ajov\'a, \v{S}koviera, and Sot\'ak of~$k$-regular graphs whose strong chromatic index equals~$2k-1$. For the second result, our main tool is the construction of Alon, Moitra, and Sudakov. We show that for every fixed~$0<\epsilon<1/2$ there exist~$\gamma>0$ and arbitrarily large~$n$ such that~$\chi_{\mathrm{S}}\bigl(n,\tbinom{n}{2}-\lfloor n^{2-\epsilon}\rfloor,P_4\bigr)\;\le\; n^{2-\gamma}=o(n^{2}).$

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

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

    math.CO 2026-07 accept novelty 6.0 of 10

    For every ε ≥ 1/2, the maximal anti-Ramsey function χ_S(n, C(n,2)−⌊n^{2−ε}⌋, P_4) exceeds n²/72 for sufficiently large n, establishing the quadratic lower bound in the complementary regime to Li–Ning–Xie's negative result.

Reference graph

Works this paper leans on

14 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

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

    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.(2013), no. 15, 1075–1096

    2013

  3. [3]

    S. A. Burr, P. Erd˝ os, P. Frankl, R. L. Graham, and V. T. S´ os, Further results on maximal anti-ramsey graphs, inGraph Theory, Combinatorics, and Applications, Vol. I, Y. Alavi, A. Schwenk (Editors), John Wiley and Sons, New York (1988), 193–206

    1988

  4. [4]

    S. A. Burr, P. Erd˝ os, R. L. Graham, and V. T. S´ os, Maximal antiramsey graphs and the strong chromatic number,J. Graph Theory13(1989), no. 3, 263–282

    1989

  5. [5]

    Buci\' c , K

    M. Buci´ c, K. Chen, and J. Ma, On a maximal anti-Ramsey conjecture of Burr, Erd˝ os, Graham, and S´ os, arXiv:2603.18952, 2026

    work page arXiv 2026

  6. [6]

    Erd˝ os, On a theorem of Rademacher-Tur´ an,Illinois J

    P. Erd˝ os, On a theorem of Rademacher-Tur´ an,Illinois J. Math6(1962), 122–127

    1962

  7. [7]

    Erd˝ os, Problems and results in combinatorial analysis and combinatorial number theory, Graph theory, combinatorics, and applications1(Kalamazoo, MI, 1988) (1991), 397–406

    P. Erd˝ os, Problems and results in combinatorial analysis and combinatorial number theory, Graph theory, combinatorics, and applications1(Kalamazoo, MI, 1988) (1991), 397–406

    1988

  8. [8]

    Erd˝ os, M

    P. Erd˝ os, M. Simonovits, and V. T. S´ os, Anti-Ramsey theorems, inInfinite and finite sets, (Colloq., Keszthely, 1973; dedicated to P. Erd˝ os on his 60th birthday), Vol. II, North Holland, Amsterdam, Vol. 10 of Colloq Math Soc J´ anos Bolyai, 633–643

    1973

Show all 14 references
  1. [9]

    Erd˝ os and T

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

    1959

  2. [10]

    F¨ uredi and D

    Z. F¨ uredi and D. S. Gunderson, Extremal numbers for odd cycles,Combin. Probab. Comput. 24(2015), 641–645

    2015

  3. [11]

    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

  4. [12]

    R. J. Faudree, R. H. Schelp, A. Gy´ arf´ as and Zs. Tuza, The strong chromatic index of graphs, Ars Combin.29(1990), 205–211

    1990

  5. [13]

    Luˇ zar, E

    B. Luˇ zar, E. M´ aˇ cajov´ a, M.ˇSkoviera, and R. Sot´ ak, Strong edge colorings of graphs and the covers of Kneser graphs,J. Graph Theory100(2022), no. 4, 686–697

    2022

  6. [14]

    G. N. S´ ark¨ ozy, and S. M. Selkow, On an anti-Ramsey problem of Burr, Erd˝ os, Graham, and T. S´ os,J. Graph Theory52(2006), no. 2, 147–156. 10

    2006

Pith tools

Reviewed June 30, 2026 · model on record in the stance chip above.