pith. sign in

arxiv: 2604.21834 · v2 · submitted 2026-04-23 · 🧮 math.CO

Anti-Ramsey numbers for cancellative configurations in p-graphs

Cheng Chi , Long-tu Yuan This is my paper

Pith reviewed 2026-05-09 21:04 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C1505C6505D10
keywords anti-Ramsey numberscancellative configurationsp-graphsedge-coloringssymmetric differencerainbow F4rainbow F5Steiner triple systems
0
0 comments X

The pith

Edge-colorings of complete p-graphs avoiding three distinct-colored edges A, B, C with A symmetric difference B contained in C use at most 1 plus floor of n over p colors.

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

The paper investigates edge-colorings of the complete p-uniform hypergraph on n vertices that avoid three edges of different colors satisfying the symmetric-difference inclusion condition. It establishes that for p at least 3 and n at least p plus 1, any such coloring uses at most 1 plus the floor of n divided by p colors. The result includes a characterization of the colorings that attain this maximum. This generalizes the classical theorem of Erdős, Simonovits and Sós from the graph case p equals 2. For the special case of p equals 3 the avoidance condition connects to two concrete forbidden rainbow configurations, yielding new relations between avoidance properties and improved upper and lower bounds on the maximum number of colors.

Core claim

We study edge-colorings of the complete p-graph on n vertices that contain no three edges A,B,C of distinct colors such that the symmetric difference of A and B is contained in C. For p≥3 and n≥p+1, we show that every such coloring contains at most 1+⌊n/p⌋ colors and characterize the extremal colorings, generalizing a theorem of Erdős, Simonovits and Sós. When p=3, the condition A△B⊆C implies |A△B|=2, and the three edges necessarily form a copy of F4 or F5. For n≥5, every rainbow F5-free edge-coloring is rainbow cancellative. For rainbow F4-free colorings, constructions and bounds are given that improve prior results.

What carries the argument

The cancellative configuration of three distinctly colored edges A, B, C where the symmetric difference of A and B is contained in C.

If this is right

  • For p=3 and n≥5 every rainbow F5-free edge-coloring is rainbow cancellative.
  • Rainbow F4-free colorings exist with m(n)+1 colors for all n≥4, where m(n) is the size of a maximum partial Steiner triple system.
  • For n=2^s−1 the anti-Ramsey number ar(n,F4) is at least m(n) + n^2/42 + o(n^2) via a Grassmann-graph construction.
  • The anti-Ramsey number ar(n,F4) is at most (5n^2−8n)/21 for n≥4, improving the quadratic coefficient from 1/4 to 5/21.

Where Pith is reading between the lines

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

  • The linear upper bound implies that extremal colorings must reuse colors according to a coarse partition of the vertex set into blocks of size roughly p.
  • The improved quadratic constructions for F4-free colorings show that design-theoretic and geometric methods can raise the achievable number of colors above the general linear threshold in special cases.
  • The implication that F5-free implies cancellative-free may extend to higher p and provide a route to proving the main bound via reduction to simpler forbidden subconfigurations.

Load-bearing premise

That the avoidance condition on symmetric differences directly implies the linear bound without additional structural assumptions on the coloring or the hypergraph beyond completeness.

What would settle it

An explicit edge-coloring of the complete p-graph on n vertices using more than 1 + floor(n/p) colors with no three edges A, B, C of distinct colors satisfying A △ B ⊆ C would disprove the bound; for example, a 4-coloring of the complete 3-graph on 7 vertices without such a triple.

Figures

Figures reproduced from arXiv: 2604.21834 by Cheng Chi, Long-tu Yuan.

Figure 1
Figure 1. Figure 1: (i) S (5) 0,3 , (ii) S (6) 4,4 , and (iii) S (4) 3,3 . Denote by T (p) the minimal2 family of p-uniform hypergraphs consisting of three edges f1, f2, f3 with [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (i) H1, and (ii) H2. 2 In the sense that if H1 ⊊ H2 and H2 ∈ T (p) , then H1 ∈ T / (p) . 4 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
read the original abstract

We study edge-colorings of the complete $p$-graph on $n$ vertices that contain no three edges $A,B,C$ of distinct colors such that the symmetric difference of $A$ and $B$ is contained in $C$. For $p\ge3$ and $n\ge p+1$, we show that every such coloring contains at most $1+\floor{n/p}$ colors and characterize the extremal colorings, generalizing a theorem of Erd\H{o}s, Simonovits and S\'os. %\cite{erdos1975}. When $p=3$, the condition $A\triangle B\subseteq C$ implies $|A\triangle B|=2$, and the three edges necessarily form a copy of $F_4\coloneqq\{abc,abd,bcd\}$ or $F_5\coloneqq\{abc,abd,cde\}$. For $n\ge5$, we show that every rainbow $F_5$-free edge-coloring is rainbow cancellative. For rainbow $F_4$-free colorings, we construct colorings with $m(n)+1$ colors for all $n\ge4$, where $m(n)$ is the size of a maximum partial Steiner triple system of order $n$ and satisfies $m(n)=n^2/6+O(n)$, improving the linear lower bound by Budden and Stiles. %\cite{budden}. Moreover, for $n=2^s-1$, we obtain $\ar(n,F_4)\ge m(n)+n^2/42+o(n^2)=4n^2/21+o(n^2)$ via a construction based on independent sets in the Grassmann graph. We also prove that $\ar(n,F_4)\le (5n^2-8n)/21$ for $n\ge4$, improving the quadratic coefficient in the upper bound of Budden and Stiles from $1/4$ to $5/21$.

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 / 2 minor

Summary. The paper investigates anti-Ramsey numbers in edge-colorings of the complete p-uniform hypergraph K_n^{(p)} that avoid a cancellative configuration: three distinct-colored edges A, B, C with A Δ B ⊆ C. For p ≥ 3 and n ≥ p+1, it proves that any such coloring uses at most 1 + ⌊n/p⌋ colors and characterizes the extremal colorings, generalizing the Erdős-Simonovits-Sós theorem. For p=3, it shows that every rainbow F_5-free coloring is cancellative-free, constructs F_4-free colorings with m(n)+1 colors (where m(n) is the size of a maximum partial Steiner triple system), obtains a quadratic lower bound of 4n²/21 + o(n²) for n=2^s-1 via Grassmann graphs, and proves an upper bound of (5n²-8n)/21, improving prior quadratic coefficients.

Significance. If the central linear bound and characterization hold, the result supplies a tight generalization of the p=2 anti-Ramsey theorem to higher uniformity under the cancellative condition, with matching constructions via matchings and monochromatic cliques. The p=3 analysis cleanly separates the stricter cancellative/F_5 condition (linear bound) from the weaker F_4 condition (quadratic bounds via partial STS and algebraic constructions), and the explicit use of known m(n) and Grassmann-graph independent sets strengthens the constructive side. These are falsifiable combinatorial statements with clear extremal examples.

minor comments (2)
  1. Abstract: the reference to the Erdős-Simonovits-Sós theorem is commented out (see %cite{erdos1975}); restore the citation in the introduction and ensure the generalization is stated with the precise p=2 statement being extended.
  2. The proof of the general upper bound (stated in the abstract for p≥3) relies on the avoidance condition directly controlling color-class sizes; a brief outline of how the symmetric-difference condition forces the linear bound without additional hypergraph assumptions would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful and accurate summary of our manuscript, the positive evaluation of its significance, and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central upper bound of 1 + floor(n/p) colors is established via a direct combinatorial argument on the avoidance of the cancellative configuration in complete p-graphs, generalizing the p=2 case of Erdős-Simonovits-Sós without reducing to fitted parameters or self-citations. The F4 and F5 distinctions for p=3 follow immediately from the symmetric difference condition, and the quadratic constructions for F4-free colorings invoke the externally known size m(n) of maximum partial Steiner triple systems rather than any internal fitting or renaming. No load-bearing step equates a prediction to its input by construction, imports uniqueness from the authors' prior work, or smuggles an ansatz via citation. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard set-theoretic and graph-theoretic axioms plus the known asymptotic size of maximum partial Steiner triple systems; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math Standard axioms of set theory and hypergraph theory for defining complete p-graphs and symmetric difference.
    Foundation for all definitions and statements.
  • domain assumption The size m(n) of a maximum partial Steiner triple system of order n satisfies m(n) = n²/6 + O(n).
    Invoked to obtain the m(n)+1 lower bound for ar(n, F4).

pith-pipeline@v0.9.0 · 5673 in / 1465 out tokens · 52203 ms · 2026-05-09T21:04:27.427277+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

22 extracted references · 22 canonical work pages

  1. [1]

    S. R. Blackburn and T. Etzion, The asymptotic behavior of Grassmannian codes,IEEE Trans. Inform. Theory,58(2012), 6605-6609

    work page 2012

  2. [2]

    Bollobás, Three-graphs without two triples whose symmetric difference is contained in a third,Discrete Mathematics,8(1974), 21-24

    B. Bollobás, Three-graphs without two triples whose symmetric difference is contained in a third,Discrete Mathematics,8(1974), 21-24

    work page 1974

  3. [3]

    Budden and W

    M. Budden and W. Stiles, Anti-Ramsey hypergraph numbers,Electronic Journal of Graph Theory and Applications,9(2) (2021), 397-407. 21

    work page 2021

  4. [4]

    Chow, On the geometry of algebraic homogeneous spaces,Annals of Mathematics,50(1) (1949), 32-67

    W. Chow, On the geometry of algebraic homogeneous spaces,Annals of Mathematics,50(1) (1949), 32-67

    work page 1949

  5. [5]

    V.Falgas-RavryandE.R.Vaughan, ApplicationsoftheSemi-DefiniteMethodtotheTuránDensityProblem for3-Graphs,Combinatorics, Probability and Computing,22(2013), 21-54

    work page 2013

  6. [6]

    C. J. Colbourn and J. H. Dinitz (Eds.), Handbook of Combinatorial Designs, 2nd ed., 2007

    work page 2007

  7. [7]

    Erdős, M

    P. Erdős, M. Simonovits and V. T. Sós, Anti-Ramsey theorems, Infinite and finite sets,Colloq. Math. Soc. János Bolyai.,10(1975), 633-643

    work page 1975

  8. [8]

    Frankl and Z

    P. Frankl and Z. Füredi, An exact result for 3-graphs,Discrete Mathematics,50(1984), 323-328

    work page 1984

  9. [9]

    Gallai, Transitiv orientierbare Graphen,Acta Math Acad Sci Hungar.,18(1967), 25-66

    T. Gallai, Transitiv orientierbare Graphen,Acta Math Acad Sci Hungar.,18(1967), 25-66

    work page 1967

  10. [10]

    R. Gu, J. Li and Y. Shi, Anti-Ramsey Numbers of Paths and Cycles in Hypergraphs,SIAM Journal on Discrete Mathematics,34(2020), 271-307

    work page 2020

  11. [11]

    M. Guo, H. Lu and X. Peng, Anti-Ramsey Number of Matchings in 3-Uniform Hypergraphs,SIAM Journal on Discrete Mathematics,37(2023), 1970-1987,

    work page 2023

  12. [12]

    Gyárfás and G

    A. Gyárfás and G. Simonyi, Edge colorings of complete graphs without tricolored triangles,Journal of Graph Theory,46(2004), 211-216

    work page 2004

  13. [13]

    Gyárfás, G

    A. Gyárfás, G. N. Sárközy, A. Sebő, and S. Selkow, Ramsey-type results for Gallai colorings,Journal of Graph Theory,64(3) (2010), 233-243

    work page 2010

  14. [14]

    Keevash, Hypergraph Turán problems,Surveys in combinatorics,392(2011), 83-140

    P. Keevash, Hypergraph Turán problems,Surveys in combinatorics,392(2011), 83-140

    work page 2011

  15. [15]

    Keevash and D

    P. Keevash and D. Mubayi, Stability theorems for cancellative hypergraphs, Journal of Combinatorial Theory, Series B,92(2004), 163-175

    work page 2004

  16. [16]

    T. P. Kirkman, On a problem of combinations,Cambridge Dublin Math. J.,2(1847), 191-204

    work page

  17. [17]

    Mantel, Problem 28,Wiskundige Opgaven,10(1907), 60-61

    W. Mantel, Problem 28,Wiskundige Opgaven,10(1907), 60-61

    work page 1907

  18. [18]

    Özkahya and M

    L. Özkahya and M. Young, Anti-Ramsey number of matchings in hypergraphs,Discrete Mathematics,313 (2013), 2359-2364

    work page 2013

  19. [19]

    Pikhurko, An exact Turán result for the generalized triangle,Combinatorica,28(2008) 187-208

    O. Pikhurko, An exact Turán result for the generalized triangle,Combinatorica,28(2008) 187-208

    work page 2008

  20. [20]

    Schönheim, On maximal systems ofk-tuples,Studia Scientiarum Mathematicarum Hungarica,1(1966), 363-368

    J. Schönheim, On maximal systems ofk-tuples,Studia Scientiarum Mathematicarum Hungarica,1(1966), 363-368

    work page 1966

  21. [21]

    Spencer, Maximal consistent families of triples,Journal of Combinatorial Theory,5(1968), 1-8

    J. Spencer, Maximal consistent families of triples,Journal of Combinatorial Theory,5(1968), 1-8

    work page 1968

  22. [22]

    Mubayi, On Hypergraphs with Every Four Points Spanning at Most Two Triples,Electronic Journal of Combinatorics,10(2003)

    D. Mubayi, On Hypergraphs with Every Four Points Spanning at Most Two Triples,Electronic Journal of Combinatorics,10(2003). 22

    work page 2003