pith. sign in

arxiv: 2606.30505 · v1 · pith:YDALZYWGnew · submitted 2026-06-29 · 🧮 math.CO

Two problems of Burr, ErdH os, Graham, and S\'os on maximal anti-Ramsey functions for P₄

Mingze Li , Bo Ning , Tianying Xie This is my paper

Pith reviewed 2026-06-30 05:04 UTC · model grok-4.3

classification 🧮 math.CO
keywords anti-Ramsey functionsP4strong edge-coloringKneser graphsgraph densityedge coloringsmaximal functions
0
0 comments X

The pith

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.

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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 γ.

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.

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.

read the original 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}).$

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

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

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

axioms (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.

pith-pipeline@v0.9.1-grok · 5923 in / 1472 out tokens · 34773 ms · 2026-06-30T05:04:18.792099+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

14 extracted references · 1 canonical work pages

  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

  9. [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

  10. [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

  11. [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

  12. [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

  13. [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

  14. [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