New Bounds on the Anti-Ramsey Number of Independent Triangles

Hongliang Lu; Xinxin Ma; Xinyue Luo

REVIEW 1 major objections 5 minor 13 references

New Bounds on the Anti-Ramsey Number of Independent Triangles

T0 review · 1 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The anti-Ramsey number of t+2 independent triangles is determined for all n ≥ 15t+57.

desk verdict Solid extension of the known anti-Ramsey threshold for independent triangles, with a genuinely new structural lemma; the main proof holds, but the abstract-threshold mismatch must be fixed. read the letter →

arxiv 2506.07115 v1 pith:BUEFUED3 submitted 2025-06-08 math.CO

Hongliang Lu , Xinyue Luo , Xinxin Ma This is my paper

classification math.CO MSC 05C5505C1505C35

keywords anti-Ramseynumberrainbowsubgraphindependenttrianglesedge-coloringTurángraphextremaltheoryvertex-disjoint

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

An edge-coloring of a complete graph is rainbow when every edge has a distinct color, and the anti-Ramsey number $ar(n,(t+2)K_3)$ is the fewest colors that force $t+2$ vertex-disjoint rainbow triangles in every coloring of $K_n$. This paper proves that for every $t \geq 0$ and every $n \geq 15t+57$ this number is exactly $\binom{t}{2}+t(n-t)+\lfloor (n-t)^2/4\rfloor+2$. The value is two more than the largest number of edges a graph on $n$ vertices can have without containing $t+1$ independent triangles, so the theorem pins the threshold exactly at the extremal bound plus two. The lower bound is achieved by the join of $K_t$ with a balanced complete bipartite graph on the remaining $n-t$ vertices, with one extra color on all other edges. The improvement is that the range where the formula is known is now linear in $t$ instead of quadratic, so the exact answer covers essentially all reasonably large $n$.

What carries the argument

The argument is carried by decomposing a maximum rainbow subgraph $G$ into a set $M$ of $t+1$ disjoint triangles and the induced leftover $D$, which must be triangle-free. The load-bearing structural tool is Lemma 4, which says that for $n_1 \geq 12t+54$ a triangle-free graph on $n_1$ vertices with at least $n_1^2/4 - n_1/2 - 6t - 11$ edges has an independent set $X$ of size at least $n_1/2 - 9$ with $d_D(x)+d_D(y) \geq 3n_1/4$ for every pair $x,y \in X$. In the application this yields common neighborhoods of size at least $n_1/4 - 9$, which is at least $4$. Those common neighbors are used repeatedly to replace triangles of $M$ by new triangles with fresh colors, so that any color repetition inside $X$ or any unwanted adjacency forces $t+2$ independent rainbow triangles. The final contradiction is assembled by showing that all edges inside a large subset $T$ of $X$ must reuse the single color of one edge of a remaining triangle, and that this forces the leftover graph to be too sparse.

What would settle it

Find, for some $t \geq 0$ and $n \geq 12t+54$, a triangle-free graph $D$ on $n$ vertices with at least $n^2/4 - n/2 - 6t - 11$ edges such that every independent set of size at least $n/2 - 9$ contains a pair of vertices with fewer than four common neighbors. Such a $D$ would satisfy Lemma 4's hypotheses but violate the common-neighborhood bound used throughout the proof, and the rainbow replacement steps would collapse. Alternatively, for $n = 15t+57$ exhibit a coloring of $K_n$ with exactly $\binom{t}{2}+t(n-t)+\lfloor (n-t)^2/4\rfloor+1$ colors and no $t+2$ independent rainbow triangles, which would directly contradict the theorem's exact value.

Watch

Extended reading notes

Core claim

The paper's central claim is the exact evaluation $ar(n,(t+2)K_3) = \binom{t}{2}+t(n-t)+\lfloor (n-t)^2/4\rfloor+2$ for $t \geq 0$ and $n \geq 15t+57$. Equivalently, $ar(n,(t+2)K_3)=ex(n,(t+1)K_3)+2$: the threshold is exactly two more than the largest number of edges in an $n$-vertex graph with no $t+1$ independent triangles. The lower bound comes from coloring the join $K_t \vee T_2(n-t)$, where $T_2(n-t)$ is the balanced complete bipartite graph on $n-t$ vertices, with the prescribed number of distinct colors and giving every other edge a single repeated color, so that no $t+2$ independent rainbow triangles can appear. The upper bound works by contradiction: take a rainbow subgraph with exactly $c(n,t)$ edges, extract $t+1$ disjoint triangles, and use the leftover triangle-free graph to manufacture one more rainbow triangle, forcing the forbidden configuration.

Load-bearing premise

The proof depends on Lemma 4's guarantee that a triangle-free leftover graph with enough edges always contains a large set of mutually nonadjacent vertices whose pairs still have at least four common neighbors; if that structural guarantee fails anywhere in the stated range, the replacement argument no longer goes through.

Editorial extensions

If this is right

For every fixed $t$, the exact value of $ar(n,(t+2)K_3)$ is now known for all $n \geq 15t+57$, and it equals $ex(n,(t+1)K_3)+2$.
The join construction $K_t \vee T_2(n-t)$, with all remaining edges given one repeated color, shows that exactly one fewer color can still avoid the configuration, so the threshold is sharp throughout the range.
Since the previous result required $n$ to be quadratic in the number of triangles, the new linear threshold removes that restriction and makes the asymptotic formula $ar(n,(t+2)K_3) = n^2/4 + (t/2)n + O(t^2)$ unconditional in the range $n \geq 15t+57$.

Reading between the lines

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

A natural conjecture the paper does not make is that the same exact formula holds for far smaller $n$ than $15t+57$; the bottleneck is the constant $9$ in the independent-set lemma, so any improvement there would immediately lower the threshold.
The replacement technique suggests a general recipe: for any fixed graph $F$ whose extremal graph is a clique join over a bipartite core, the anti-Ramsey number for vertex-disjoint copies of $F$ should have a linear threshold in the number of copies, with the same 'one color on a large independent set' compression appearing.
For small $t$, the critical behavior near $n = 15t+57$ could be checked by computer search: a coloring of $K_n$ with exactly one fewer color than the claimed value and no $t+2$ independent rainbow triangles would mark where the linear threshold becomes necessary, although the theorem already covers all larger $n$.

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: the paper proves a real improvement—the exact anti-Ramsey value for (t+2)K3 now holds for n ≥ 15t+57 instead of the previous quadratic threshold. The formula itself is Wu et al.'s; the new content is a much wider range, obtained through a sharpened counting argument. Lemma 4 is the kernel: in a K3-free graph with near-extremal edge count, you get a large independent set whose vertices have pairwise large common neighborhood. That lemma is correct and is what drives the whole proof.

I went through the main inequalities and the replacement arguments. They check out. The notation M is overloaded (the triangle collection and the maximum matching in D), but reading A and B as a partition of the triangles and M as the matching keeps everything coherent. The lower-bound construction is terse around the role of T2, but the missing argument is standard: a rainbow (t+2)K3 can use at most one edge of color 0, so at most one triangle avoids H, and the remaining t+1 triangles force t+1 distinct vertices from K_t, impossible. So the proof is sound.

Soft spots are mostly presentational. The abstract states the threshold for kK3 as n ≥ 15k+57, but the theorem gives n ≥ 15t+57 for (t+2)K3, i.e., n ≥ 15k+27 in k-notation. That mismatch is confusing and should be corrected; it is not a mathematical error, just an indexing slip that makes the abstract read as a different (weaker) bound. There are also a few places where claims are asserted with minimal justification—Claim 4 in particular deserves one more sentence about why the set of bad pairs has size at most t, and the last step of Claim 8 is quick. None of these are load-bearing; the missing details are standard and can be filled.

The paper cites the prior work honestly and does not fit parameters to its conclusion. It is a useful contribution for anyone working on anti-Ramsey numbers of disjoint fixed subgraphs. It deserves a serious referee; I would send it to review after the authors fix the abstract-threshold mismatch and expand the terse claims.

Referee Report

1 major / 5 minor

Summary. The paper determines the exact anti-Ramsey number of t+2 vertex-disjoint triangles for n≥15t+57, proving ar(n,(t+2)K3)=binom(t,2)+t(n−t)+floor((n−t)^2/4)+2. The lower bound is obtained by coloring Kt∨T2(n−t) with ex(n,(t+1)K3)+1 colors. The upper bound starts from any rainbow subgraph with ex+2 edges, selects a copy of (t+1)K3, partitions its triangles into types A and B, and uses the matching number of the remaining K3-free graph D together with Moon's theorem and a new extremal lemma to force a rainbow (t+2)K3. The proof is a self-contained counting argument; the threshold constants are chosen to make the inequalities work, and no parameter is fitted to the target formula.

Significance. If correct, the result extends exact anti-Ramsey numbers for independent triangles from a quadratic threshold to a linear threshold in the number of triangles, improving the earlier range n≥2k²−k+2 for k≥10. The central inequalities (1)–(15) are algebraically sound, and Lemma 4—the most delicate structural input—is valid: deleting eight low-degree vertices removes fewer than 3n edges, and the resulting edge count contradicts Moon's theorem. The proof does not assume the target formula, and the main weaknesses are presentational, notably an inconsistent statement of the threshold in the abstract.

major comments (1)

[Abstract] The abstract states that the lower bound on n is improved to n≥15k+57 for ar(n,kK3). Since Theorem 3 concerns (t+2)K3 with n≥15t+57, setting k=t+2 gives n≥15k+27, not 15k+57. The abstract's bound is therefore incorrect; moreover, 15k+27 improves on Wu et al.'s 2k²−k+2 only for k≥10, so the improvement claim should be qualified. Please correct the abstract and align the parameterization with Theorem 3.

minor comments (5)

[Section 2, proof of Theorem 3] The symbol M is used both for the collection of t+1 triangles and for a maximum matching of D; e.g., 'Let γ:=ν(D) and let M be a maximum matching of D' is immediately followed by 'The triangles of M may be partitioned...'. Rename the matching, say M̃, to remove the ambiguity.
[Claim 1] The quadratic 5a²/4+a(n/2−6(t+1)−2)+(n−6(t+1))²/4 attains its maximum on 0≤a≤t−1 at a=t−1 when n≥(19t+37)/2, not at n≥19t/2+35/2 as stated. Under the theorem's assumption n≥15t+57 the intended conclusion still holds, but the stated condition is inaccurate.
[Lemma 4] The application of Theorem 1 is with t=0, i.e., Mantel's theorem; the proof should say this explicitly and note that the strict inequality e(G′)>floor((n−8)²/4) is what yields the contradiction.
[Claims 7 and 8] The line 'Since T ≥ n1/4−9−2t≥4' should read 'Since |T| ≥ ...'; also, the expression '(z1,p1_1,q1_1)∪(x1,y1,zt+1)' should be written as two separate triples in the display.
[Lemma 5] The sentence 'Since T2(n−t) contains no rainbow triangles' is imprecise; T2(n−t) is triangle-free, and the conclusion that there are at most t independent triangles follows because every triangle in Kt∨T2(n−t) uses a vertex of Kt.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the proof is a self-contained counting argument built on independent external theorems (Moon 1968); there are no self-citations, no fitted parameters, and the target formula is never assumed as an input.

full rationale

The paper contains no circular derivation. The target value ar(n,(t+2)K3) = binom(t,2) + t(n−t) + floor((n−t)^2/4) + 2 equals ex(n,(t+1)K3) + 2 by Moon's external theorems (Theorem 1, Lemma 2), and the proof never assumes this value as an input. The lower bound (Lemma 5) is self-contained: color E(Kt ∨ T2(n−t)) rainbow and all other edges of K_n with one new color; because each independent triangle must use at least one vertex of the K_t part, at most t fit, so this ex+1-coloring has no rainbow (t+2)K3. The upper bound is a contradiction counting argument: from an ex+2-coloring with no rainbow (t+2)K3, the paper extracts a rainbow subgraph G with ex+2 edges, finds a (t+1)K3 by Moon's theorem, bounds edges incident to it via inequalities (1)–(6), and contradicts e(G) = ex+2. Lemma 4, the flagged assumption, is proved in-paper by a short deletion argument using only Mantel/Moon and the hypothesis n ≥ 12t+54; its constants are chosen to make the inequality e(G′) > (n−8)^2/4 hold, not to reproduce the theorem. Claims 1–8 are replacement arguments that build rainbow (t+2)K3 from the rainbow distinctness of G; none invokes the conclusion. There are no fitted parameters, and none of the 13 references overlaps with the present authors, so no self-citation is load-bearing. The reuse of the symbol M for both the triangle collection and a maximum matching of D is a presentation flaw that resolves on disambiguation (A and B partition the triangle collection; the later M is a matching of D) and is editorial, not circular. The extension of Wu et al.'s valid range from quadratic to linear is a genuine incremental contribution, not a renaming.

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

The proof introduces no new entities or fitted parameters. It relies on two classical theorems of Moon and standard properties of Turán graphs. The constants 15, 57, 12, 54, 6, 11 are fixed integers chosen to satisfy the inequalities; they are not fitted and the theorem is the assertion for exactly those constants.

assumptions (3)

standard math Moon's theorem (Theorem 1): If I_3(G)=t and n > 9t/2+4, then e(G) ≤ binom(t,2) + t(n-t) + floor((n-t)^2/4), with equality only for K_t ∨ T_2(n-t).
Used in Lemma 4 to show a K3-free graph containing too many edges after deleting low-degree vertices must contain a K3.
standard math Moon's Lemma 2: If ν(G)=h and I_3(G)=0, then e(G) ≤ h(n-h), with equality for K_{h,n-h}.
Used to bound edges in the triangle-free leftover graph D.
standard math Turan graph T_2(n-t) is bipartite and hence triangle-free.
Used in the lower-bound construction to ensure no rainbow triangle inside the bipartite part.

how reviews work

0 comments

Cite this review

Pith. "Pith review of New Bounds on the Anti-Ramsey Number of Independent Triangles." pith.science (2026). https://pith.science/paper/BUEFUED3

@misc{pith2026250607115,
  author       = {Pith},
  title        = {Pith review of: New Bounds on the Anti-Ramsey Number of Independent Triangles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BUEFUED3}},
  note         = {Machine review of arXiv:2506.07115}
}

abstract

An edge-colored graph is called \textit{rainbow graph} if all the colors on its edges are distinct. Given a positive integer $n$ and a graph $G$, the \textit{anti-Ramsey number} $ar(n,G)$ is defined to be the minimum number of colors $r$ such that there exists a rainbow copy of $G$ in any exactly $r$-edge-coloring of $K_n$. Wu et al. (Anti-Ramsey numbers for vertex-disjoint triangles, \emph{Discrete. Math.}, \textbf{346} (2022), 113123) determined the anti-Ramsey number $ar(n, kK_3)$ for $n\geq 2k^2-k+2 $. In this paper, we extend this result by improving the lower bound on $n$ to $n\geq 15k+57$.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

13 extracted references · 12 canonical work pages

[1]

H. Chen, X. Li and J. Tu, Complete solution for the rainbow numbers of matchings, Discrete Math. , 309 (2009), 3370–3380

work page 2009
[2]

Erd˝ os, M

P. Erd˝ os, M. Simonovits and V. S´ os, Anti-Ramsey theore ms, Inﬁnite and Finite sets (Colloq. Keszthely 1973), Colloq. Math. Soc. J´ anos Bolyai , 10 (1975), 633–643

work page 1975
[3]

Erd˝ os and T

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

work page 1959
[4]

Erd˝ os, ber ein Extremalproblem in der Graphentheori e (German), Arch

P. Erd˝ os, ber ein Extremalproblem in der Graphentheori e (German), Arch. Math. , 13 (1962), 122–127

work page 1962
[5]

Kaneko, I

Fujita, A. Kaneko, I. Schiermeyer and K. Suzuki, A rainbo w k-matching in the complete graph with r-colors, Electron J. Combin. , 16 (2009), R51

work page 2009
[6]

Haas and M

R. Haas and M. Young, The anti-Ramsey number of perfect ma tching, Discrete Math. , 312 (2012), 933–937

work page 2012
[7]

Jahanbekam and D

S. Jahanbekam and D. West, Anti-Ramsey problems for t edg e-disjoint rainbow spanning subgraphs: cycles, matchings, or trees, J. Graph Theory , 82 (2016), 75–89

work page 2016
[8]

Montellano-Ballesteros and V

J. Montellano-Ballesteros and V. Neumann-Lara, An anti -Ramsey theorem, Combinator- ica, 22 (2002), 445–449

work page 2002

Show all 13 references

[9]

Montellano-Ballesteros and V

J. Montellano-Ballesteros and V. Neumann-Lara, An anti -Ramsey theorem on cycles, Graphs Combin. , 21 (2005), 343–354. 10

2005
[10]

Moon, On independent complete subgraphs in a graph, Canad

W. Moon, On independent complete subgraphs in a graph, Canad. J. Math. , 20 (1968), 95–102

1968
[11]

Schiermeyer, Rainbow numbers for matchings and comp lete graphs, Discrete Math

I. Schiermeyer, Rainbow numbers for matchings and comp lete graphs, Discrete Math. , 286 (2004), 157–162

2004
[12]

F. Wu, S. Zhang, B. Li and J. Xiao, Anti-Ramsey numbers fo r vertex-disjoint triangles, Discrete Math. , 346 (2022), 113123

2022
[13]

Yuan and X

L. Yuan and X. Zhang, Anti-Ramsey numbers of graphs with some decomposition family sequences, arXiv:1903.10319[math.CO]. 11

1903 arXiv

Pith tools

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

[1] [1]

H. Chen, X. Li and J. Tu, Complete solution for the rainbow numbers of matchings, Discrete Math. , 309 (2009), 3370–3380

work page 2009

[2] [2]

Erd˝ os, M

P. Erd˝ os, M. Simonovits and V. S´ os, Anti-Ramsey theore ms, Inﬁnite and Finite sets (Colloq. Keszthely 1973), Colloq. Math. Soc. J´ anos Bolyai , 10 (1975), 633–643

work page 1975

[3] [3]

Erd˝ os and T

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

work page 1959

[4] [4]

Erd˝ os, ber ein Extremalproblem in der Graphentheori e (German), Arch

P. Erd˝ os, ber ein Extremalproblem in der Graphentheori e (German), Arch. Math. , 13 (1962), 122–127

work page 1962

[5] [5]

Kaneko, I

Fujita, A. Kaneko, I. Schiermeyer and K. Suzuki, A rainbo w k-matching in the complete graph with r-colors, Electron J. Combin. , 16 (2009), R51

work page 2009

[6] [6]

Haas and M

R. Haas and M. Young, The anti-Ramsey number of perfect ma tching, Discrete Math. , 312 (2012), 933–937

work page 2012

[7] [7]

Jahanbekam and D

S. Jahanbekam and D. West, Anti-Ramsey problems for t edg e-disjoint rainbow spanning subgraphs: cycles, matchings, or trees, J. Graph Theory , 82 (2016), 75–89

work page 2016

[8] [8]

Montellano-Ballesteros and V

J. Montellano-Ballesteros and V. Neumann-Lara, An anti -Ramsey theorem, Combinator- ica, 22 (2002), 445–449

work page 2002