Anti-Ramsey number of intersecting cliques

Hongliang Lu; Xinxin Ma; Xinyue Luo

REVIEW 4 major objections 7 minor 19 references

Anti-Ramsey number of intersecting cliques

T0 review · 4 major / 7 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read For every $k \ge 1$ and $r \ge 2$, all sufficiently large complete graphs satisfy $ar(n,F_{k+1,r})=ex(n,F_{k,r})+2$.

desk verdict The result is likely right and the paper is earnest, but the proof has several load-bearing gaps — the most serious being Lemma 9's unjustified domination claim — so I would send it back for major revision rather than desk-reject it. read the letter →

arxiv 2507.13165 v1 pith:SB6AAURG submitted 2025-07-17 math.CO

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

classification math.CO MSC 05C5505C3505C15

keywords anti-RamseynumberrainbowsubgraphintersectingcliquesfangraphTuránextremaledge-coloring

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

This paper determines the exact anti-Ramsey number of the fan graph $F_{k+1,r}$: the graph made from $k+1$ cliques of size $r$ that all meet in one common vertex. For every $k \ge 1$, $r \ge 2$, and every $n \ge 256(k+1)^5 r^{16}$, it proves $ar(n,F_{k+1,r}) = ex(n,F_{k,r}) + 2$. In words, the smallest number of colors that forces a rainbow copy of the larger fan is exactly two more than the Turán number of the one-step-smaller fan. Exact anti-Ramsey values are rare, and this one pins down the threshold behavior for a whole family of intersecting-clique graphs at once.

What carries the argument

The named object is the $(k,r)$-fan $F_{k,r}$: $k$ cliques of size $r$ sharing exactly one vertex. The identity doing the work is $ar(n,F_{k+1,r}) = ex(n,F_{k,r})+2$. The proof machinery is a partition lemma (Lemma 9) that takes an $F_{k+1,r}$-free graph with high minimum degree and more than $ex(n,F_{k,r})$ edges and cuts it into $r-1$ parts $V_0\cup\dots\cup V_{r-2}$, each of size about $n/(r-1)$, with internal matching number at most $k$, internal maximum degree at most $k$, and every pair of parts mutually dominating with bounded deficiency, meaning each vertex in one part is nonadjacent to only a bounded number of vertices in every other part. The auxiliary sets $X_i$ are common neighborhoods of leaves in a maximum clique through the center; the paper's claims and Lemmas 7, 8 and 10 turn these neighborhood sets into the final partition and control the edge count.

What would settle it

Check the application of Lemma 8 inside Lemma 9 with $Y_0=N_{X_0}(x_0)$ and $Y_i=N_{X_i}(x_0)$: if some vertex of $Y_0$ has fewer than $|Y_i|-2(k+1)(r-1)$ neighbors in $Y_i$, the claimed $k+1$ disjoint cliques of size $r-1$ are not delivered. Exhibiting such a graph that still satisfies the earlier claims of Lemma 9, or an exact coloring of $K_n$ with $ex(n,F_{k,r})+1$ colors and no rainbow $F_{k+1,r}$, would settle the matter.

Watch

Extended reading notes

Core claim

The central result is exact: for every $k \ge 1$, $r \ge 2$ and $n \ge 256(k+1)^5 r^{16}$, the anti-Ramsey number $ar(n,F_{k+1,r})$ equals $ex(n,F_{k,r})+2$. The lower bound follows from the standard inequality relating anti-Ramsey numbers to Turán numbers of one-edge-deleted graphs. The upper bound is proved by contradiction. Starting from a rainbow subgraph $G$ with $ex(n,F_{k,r})+2$ edges that is $F_{k+1,r}$-free, Lemma 9 produces a partition of $V(G)$ into $r-1$ large parts with bounded internal structure and almost-complete cross pairs. Lemma 10 and the known extremal characterization then force the cross graph to be essentially a balanced complete $(r-1)$-partite graph, and the remaining edges spill into one part whose matching structure lets the proof rebuild the forbidden rainbow fan.

Load-bearing premise

The proof of Lemma 9 needs a two-way near-completeness between the central auxiliary set and each of the other auxiliary sets, but it establishes only the one-way direction (each outer set is almost completely connected to the central one); if the missing reverse direction fails, the clique-extension step used to force a rainbow fan is not justified.

Editorial extensions

If this is right

Every exact edge-coloring of $K_n$ with $ex(n,F_{k,r})+2$ colors contains a rainbow $(k+1,r)$-fan whenever $n \ge 256(k+1)^5 r^{16}$.
The extremal rainbow-free colorings are structured: they differ from a balanced complete $(r-1)$-partite coloring only inside one part, whose internal graph has bounded matching number and bounded degree.
The asymptotic value of the anti-Ramsey number is $\frac{r-2}{2(r-1)}n^2 + O(1)$, so the threshold is essentially the Turán density of $K_r$ plus a constant shift of 2.
For $r=3$ the result recovers the earlier triangle-fan case; for general $r$ it completes the picture opened by the extremal formula for intersecting cliques.

Reading between the lines

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

The threshold $n \ge 256(k+1)^5 r^{16}$ is an artifact of the proof's inequalities; a natural test is whether the range can be improved to something like $n \ge C k^2 r^4$, matching the order used in the extremal theorem.
When $r=2$, the theorem says $ar(n,K_{1,k+1}) = \lfloor n(k-1)/2 \rfloor + 2$ for large $n$; checking this star case against known anti-Ramsey results would give a clean, concrete test of the general machinery.
The pattern $ar(n,H^+)=ex(n,H)+2$ for $H^+$ obtained by adding one more clique to a fan suggests a broader gluing principle for graphs built around a common cut vertex, though the paper does not state such a conjecture.

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

Bottom line: this is a serious attempt at the right theorem, and the formula ar(n,F_{k+1,r}) = ex(n,F_{k,r}) + 2 for r≥4 is the natural extension of the friendship-graph case. The lower bound is immediate from (1), and the upper-bound strategy — following Chen et al.'s extremal decomposition — is a reasonable program. The paper reads as an honest, knowledgeable piece of work, and the r=3 case it relies on is the authors' own preprint, which is not load-bearing for the new r≥4 range. I'm not accusing the authors of anything; the gaps are mathematical, not attitudinal.

But as written, the proof does not support the theorem. In Lemma 9's Claim 5, the application of Lemma 8 needs Y_j to dominate Y_i for every ordered pair, where Y_i = N_{X_i}(x0) are small subsets of the large sets X_i. Claim 3 only gives domination between the X_i's, and only when the source is not X_0. Even for j>0, the inference from 'x in X_j has almost all of X_i as neighbors' to 'x has almost all of the tiny set Y_i as neighbors' is not valid unless Y_i is almost all of X_i. So the k+1 disjoint (r−1)-cliques inside N(x0) are not established, and the bound on X0* has no support. That is load-bearing. Separately, Lemma 10 is stated with literal '(??)' placeholders for its hypotheses; in a serious paper, a lemma with an incomplete statement cannot be used. The r=2 case in Theorem 1 is never touched: Lemma 9 only works for r≥4, and the partition into r−1 parts is meaningless for r=2. Finally, the new Claim 5 in Section 4 goes from a rainbow K1,k+1 or matching in H[Vi] to one in G[V0] without argument; the representative subgraph G need not contain the same vertex pattern, only the same colors.

None of this means the theorem is false. I think it's likely true, and a motivated expert could probably repair the domination step or replace the argument. But a referee cannot verify the current proof, and the paper is not acceptable in this state.

Who is it for? Specialists in extremal graph theory / anti-Ramsey numbers, especially those who know Chen et al.'s extremal graph decomposition. It deserves a serious referee — the question is important enough and the approach is plausible — but the report should demand a substantial revision: repair Lemma 9, state Lemma 10 properly, handle r=2, and justify the H→G transfer. I would not cite the current version.

Referee Report

4 major / 7 minor

Summary. The paper claims to determine the anti-Ramsey number of the (k,r)-fan F_{k+1,r} for all k ≥ 1, r ≥ 2, and n ≥ 256(k+1)^5 r^{16}, proving ar(n,F_{k+1,r}) = ex(n,F_{k,r}) + 2. The lower bound is the standard inequality ar(n,G) ≥ ex(n,{G−e}) + 2. For the upper bound, the authors choose a rainbow subgraph G with one edge from each color class, then split the proof according to whether δ(G) is large or small. In the large-degree case, Lemma 9 partitions V(G) into r−1 parts with degree and matching-number bounds, Lemma 10 converts this into a lower bound on the number of cross-edges, and a final argument forces the internal parts to be extremal and then produces a rainbow F_{k+1,r}. The small-degree case iteratively deletes low-degree vertices and applies Lemma 4. The proof relies heavily on Lemmas 7, 8, and 10 from Chen et al. [4].

Significance. If the proof were complete, the theorem would give the exact anti-Ramsey number for intersecting cliques for all fixed k and r and all sufficiently large n, extending the friendship-graph case r = 3 and fitting the Erdős–Simonovits–Sós paradigm in which the anti-Ramsey number exceeds the corresponding Turán number by 2. The lower bound is standard and the overall strategy is coherent. However, the manuscript as written contains several load-bearing gaps: Lemma 10 is stated with placeholder hypotheses, the application of Lemma 8 in Lemma 9 does not verify the domination hypothesis, a rainbow subgraph in H is incorrectly transferred to G in Section 4, and the claimed range r ≥ 2 is not covered by the proof, which only treats r ≥ 4. The result is plausible and likely repairable, but the current proof is not acceptable as a complete argument.

major comments (4)

[§3, Claim 5 (and Claim 6) of Lemma 9] The application of Lemma 8 does not verify its domination hypothesis. With b = 2(k+1)(r−1) and Y_i = N_{X_i}(x0), the proof only establishes via Claim 3 that the full sets X_i dominate X_j; it does not establish that the smaller sets Y_i dominate each other. For x ∈ Y_j, Claim 3 gives d_{X_i}(x) ≥ |X_i| − b, but Lemma 8 requires d_{Y_i}(x) ≥ |Y_i| − b, and |X_i| − |Y_i| can be much larger than b. The required statement that Y0 dominates Y_i is never proved, and the same issue affects positive indices j. Since the k+1 disjoint (r−1)-cliques produced by Lemma 8 are exactly what force the contradiction in Claim 5, the bound |X0^*| ≤ 2(k+1)(r−1)(r−2) is unsupported, and the partition in Lemma 9 collapses. Claim 6 repeats the same unverified Lemma 8 application and also refers to cliques in N(x0) when the center should be the vertex v under consideration.
[§4, Lemma 10] Lemma 10 is stated with '(??)' placeholders in place of its hypotheses. This is not a cosmetic issue: Lemma 10 is used immediately after Lemma 9 to derive inequality (12), which is the starting point for the bound on t and for the subsequent construction of the sets V'_i and S_i. Without a precise statement of the hypotheses, or a proof that they are satisfied by the partition from Lemma 9, the derivation of (12) is incomplete.
[§4, Claim 5] The proof of Claim 5 assumes that if H[V_i] contains a rainbow K_{1,k+1} or (k+1)K2, then 'without loss of generality' G[V_0] contains the same subgraph. This is not justified: G was chosen as a set of one representative edge per color class of H, so for each color used by a rainbow subgraph of H, the representative edge in G may lie outside V_i. The claim is used to force the monochromatic matchings M_i and hence the extremal conclusion G' ∈ EX(n,F_{k,r}); without a correct argument the final contradiction is not established.
[Theorem 1 vs. Lemma 9] Theorem 1 is stated for all r ≥ 2, but Lemma 9 is proved only for r ≥ 4. The proof of Theorem 1 invokes Lemma 9 in Case 1 without restriction on r, and no separate treatment of r = 2 is given; the r = 3 case is mentioned in the introduction as following from Liu–Lu–Luo [14], but this reduction is not carried out in the proof. As written, the proof does not cover the full range claimed in the theorem.

minor comments (7)

[§3, Claim 3 proof] The displayed inequality uses d_G(x_i) where it should use d_G(x) for the chosen vertex x ∈ X_i; as printed, the line does not make sense.
[§3, Claim 6] The phrase 'there are k+1 vertex disjoint cliques of size r−1 in N(x0)' should read N(v), the vertex whose exclusion is being tested; x0 is not defined in Claim 6.
[§4, Case 2] The displayed condition 'δ(G_t) ≥ (r−2)/(r−1)l − (k+1)' should be 'δ(G_t) ≥ (r−2)/(r−1)(n−l) − (k+1)'.
[§4, Claim 6 proof] The expression 'F_{k+1,R}' should be 'F_{k+1,r}'.
[§4, after Claim 6] The inequality labeled (15), 'e(G') ≥ ex(n,F_{k+1,r})', should be 'e(G') ≥ ex(n,F_{k,r})' for the subsequent equality argument to work.
[Throughout] The label 'Claim 5' is used both inside Lemma 9 and in Section 4; renumbering would avoid confusion.
[§3, Claim 1 proof] The phrase 'replacing vi by the edge uv in D' should refer to the clique K, not D.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation relies on independent external extremal results and structural lemmas, and no step reduces the target identity to its own inputs.

full rationale

The paper's main theorem, ar(n, F_{k+1,r}) = ex(n, F_{k,r}) + 2, is obtained from a standard lower bound via the Erdős–Simonovits–Sós inequality together with the observation that F_{k,r} is the relevant edge-deleted subgraph of F_{k+1,r}, and from an upper bound by contradiction using external structural results of Chen, Gould, Pfender, and Wei (Lemmas 4, 7, 8, 10 and Theorem 6), Chvátal–Hanson (Theorem 3), and Turán's theorem. No parameter is fitted to the answer, and the target anti-Ramsey quantity is not used as an input to the extremal theorems. The only self-citation, [14], concerns the special case r = 3 and is mentioned in the introduction; it is not used in the proof of the new r ≥ 4 cases, so it is not load-bearing. The identified issue in Lemma 9 regarding the direction of domination when applying Lemma 8 is a possible correctness gap in the proof, not a circularity: it does not make the conclusion equivalent to an assumption or to a self-citation. Hence the circularity score is 0.

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

The central claim rests on known extremal results (Chen et al., Chvatal-Hanson, Turan) and on an unproved domination property inside Lemma 9's decomposition. No free parameters are fitted; the large constants are choice bounds for inequalities. No new entities are introduced.

assumptions (6)

standard math Turan theorem: ex(n,K_r)=t_{r-1}(n)
Used throughout Section 4 to compute ex(n,K_r) and the cross-edge bound (12)-(13).
domain assumption Theorem 6 (Chen et al.): exact ex(n,F_{k,r}) and extremal structure
Load-bearing for the final step identifying G' with an extremal graph; stated in the introduction, used in Claim 6 of Section 4.
domain assumption Lemma 10 (Chen et al.): inequality relating e(G_i) and cross edges
Quoted in Section 2 with '(??)' hypotheses; necessary in Case 1 to bound t and e(G_i).
standard math Chvatal-Hanson theorem: f(nu,Delta)
Used to bound e(G_i) and to identify the embedded extremal graph.
standard math Abbott-Hanson-Sauer values of f(k,k)
Used in Theorem 2 and in the bound (16) in Case 2.
ad hoc to paper Uncited monochromatic matching lemma
The proof asserts that H[S_i] with no rainbow (k+1)-matching contains a monochromatic matching of size at least 5k^2r^7; no proof or citation is given.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Anti-Ramsey number of intersecting cliques." pith.science (2026). https://pith.science/paper/SB6AAURG

@misc{pith2026250713165,
  author       = {Pith},
  title        = {Pith review of: Anti-Ramsey number of intersecting cliques},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SB6AAURG}},
  note         = {Machine review of arXiv:2507.13165}
}

abstract

An edge-colored graph is called a rainbow graph if all its edges have distinct colors. The anti-Ramsey number $ar(n, G)$, for a graph $G$ and a positive integer $n$, is defined as the minimum number of colors $r$ such that every exact $r$-edge-coloring of the complete graph $K_n$ contains at least one rainbow copy of $G$. A $(k, r)$-fan graph, denoted $F_{k, r}$, is a graph composed of $k$ cliques each of size $r$, all intersecting at exactly one common vertex. In this paper, we determine $ar(n, F_{k, r})$ for $n \geq 256r^{16}(k+1)^5$, $k \geq 1$, and $r \geq 2$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[4]

G. Chen, R. Gould, F. Pfender, and B. Wei, Extremal graphs for intersecting cliques, J. Combin. Theory Ser. B , 89(2003), 159–171

work page 2003
[14]

W. Liu, H. Lu and X. Luo, Anti-Ramsey Number of Friendship Graphs, preprint

work page
[1]

Abbott, D

H. Abbott, D. Hanson and N. Sauer, Intersection theorems for systems of sets, J. Combin. Theory Ser. A , 12 (1972), 381–389

work page 1972
[2]

Alon, On a conjecture of Erd˝ os, Simonovits and S´ os concerning anti-Ramsey theorems, J

N. Alon, On a conjecture of Erd˝ os, Simonovits and S´ os concerning anti-Ramsey theorems, J. Graph Theory , 7 (1983), 91–94

work page 1983
[3]

Chv´ atal and D

V. Chv´ atal and D. Hanson, Degrees and matchings,J. Combin. Theory Ser. B , 20 (1976), 128–138

work page 1976
[5]

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

work page 2009
[6]

Erd˝ os and A.H

P. Erd˝ os and A.H. Stone, On the structure of linear graphs,Bull. Amer. Math., 52 (1946), 1089–1091

work page 1946
[7]

Erd˝ os, and T

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

work page 1959

Show all 19 references

[8]

Erd˝ os, M

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

1975
[9]

Erd˝ os, Z

P. Erd˝ os, Z. F¨ uredi, R.J. Gould and D.S. Gunderson, Extremal graphs for intersecting triangles, J. Combin. Theory Ser. B , 64 (1995), 89–100

1995
[10]

Fujita, C

S. Fujita, C. Magnant and K. Ozeki, Rainbow generalizations of Ramsey theory: a survey, Graphs Combin., 26 (2010), 1–30

2010
[11]

Gilboa, and Y

S. Gilboa, and Y. Roditty, Anti-Ramsey numbers of graphs with small connected compo- nents, Graphs Combin., 32 (2016), 649–662

2016
[12]

Haas, and M

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

2012
[13]

Jiang, I

T. Jiang, I. Schiermeyer and D.B. West, The Erd˝ os-Simonovits-S´ os conjecture fork ≤ 7, unpublished manuscript
[15]

Montellano-Ballesteros and V

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

2002
[16]

Montellano-Ballesteros and V

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

2005
[17]

Schiermeyer, Rainbow numbers for matchings and complete graphs, Discrete Math

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

2004
[18]

F. Wu, S. Zhang, B. Li and J. Xiao, Anti-Ramsey numbers for vertex-disjoint triangles, Discrete Math., 346 (2023), 113–123

2023
[19]

Yuan and X

L. Yuan and X. Zhang, Anti-Ramsey numbers of graphs with some decomposition family sequences, arXiv:1903.10319 , 2019. 14

1903 arXiv

Pith tools

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

[1] [4]

G. Chen, R. Gould, F. Pfender, and B. Wei, Extremal graphs for intersecting cliques, J. Combin. Theory Ser. B , 89(2003), 159–171

work page 2003

[2] [14]

W. Liu, H. Lu and X. Luo, Anti-Ramsey Number of Friendship Graphs, preprint

work page

[3] [1]

Abbott, D

H. Abbott, D. Hanson and N. Sauer, Intersection theorems for systems of sets, J. Combin. Theory Ser. A , 12 (1972), 381–389

work page 1972

[4] [2]

Alon, On a conjecture of Erd˝ os, Simonovits and S´ os concerning anti-Ramsey theorems, J

N. Alon, On a conjecture of Erd˝ os, Simonovits and S´ os concerning anti-Ramsey theorems, J. Graph Theory , 7 (1983), 91–94

work page 1983

[5] [3]

Chv´ atal and D

V. Chv´ atal and D. Hanson, Degrees and matchings,J. Combin. Theory Ser. B , 20 (1976), 128–138

work page 1976

[6] [5]

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

work page 2009

[7] [6]

Erd˝ os and A.H

P. Erd˝ os and A.H. Stone, On the structure of linear graphs,Bull. Amer. Math., 52 (1946), 1089–1091

work page 1946

[8] [7]

Erd˝ os, and T

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

work page 1959