pith. sign in

arxiv: 2605.04783 · v2 · submitted 2026-05-06 · 🧮 math.CO

The maximum number of triangles in graphs without vertex disjoint friendship graphs

Wanfang Chen , Jia-Bao Yang , Leilei Zhang This is my paper

Pith reviewed 2026-05-08 16:12 UTC · model grok-4.3

classification 🧮 math.CO
keywords generalized Turán numberfriendship graphextremal graph theorytriangle copiesvertex-disjoint copiesforbidden disjoint union
0
0 comments X

The pith

The maximum number of triangles in n-vertex graphs without t+1 vertex-disjoint friendship graphs F_k is determined exactly, with the extremal graphs characterized.

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

This paper establishes the exact value of the generalized Turán number ex(n, K_3, (t+1)F_k), which counts the largest number of triangles in an n-vertex graph that contains no t+1 vertex-disjoint copies of the friendship graph F_k. A sympathetic reader would care because the extremal graphs for this forbidden configuration differ fundamentally from those that avoid only a single copy of F_k. The result extends earlier work on single friendship graphs and resolves an open case from prior studies of similar forbidden disjoint unions. It demonstrates that increasing the number of allowed disjoint copies alters the optimal structure in a way not seen in previous analogous problems.

Core claim

The paper determines the value of ex(n, K_3, (t+1)F_k) for integers t ≥ 1 and k, and characterizes the extremal graphs. In contrast to the extremal graphs for a single F_k, those for (t+1)F_k undergo a fundamental structural change. This structure is also different from those arising in previous similar problems on generalized Turán numbers.

What carries the argument

The generalized Turán number ex(n, K_3, (t+1)F_k), which records the maximum number of K_3 copies in an n-vertex graph free of t+1 vertex-disjoint F_k copies; the argument turns on identifying the new optimal constructions that achieve this maximum.

Load-bearing premise

The extremal graphs for avoiding t+1 disjoint copies of F_k undergo a fundamental structural change from the single F_k case, and the proposed construction is optimal for every t ≥ 1 and every k.

What would settle it

An n-vertex (t+1)F_k-free graph whose number of triangles exceeds the claimed value for ex(n, K_3, (t+1)F_k) would falsify the determination of the extremal number.

Figures

Figures reproduced from arXiv: 2605.04783 by Jia-Bao Yang, Leilei Zhang, Wanfang Chen.

Figure 1
Figure 1. Figure 1: Construct Hn(P, Q, R) from a k-admissible triple (P, Q, R). For convenience, we let τR(P, Q) = X aa′∈E(P) |NR(a) ∩ NR(a ′ )| + X bb′∈E(Q) |NR(b) ∩ NR(b ′ )| (3) and Φ(P, Q, R, t) = (2f(k − 1, k − 1) − |A||B| + e(R))t − f(k − 1, k − 1)(|A| + |B|) +N(K3, P) + N(K3, Q) + τR(P, Q). (4) Since Pk is finite and there are only finitely many choices for R ⊆ A × B, the number c ∗ k (t) = max{Φ(P, Q, R, t) : (P, Q, R… view at source ↗
Figure 2
Figure 2. Figure 2: Construction of the graph G. Claim 10. For every a ∈ A and b ∈ B, we have dP (a) + ν view at source ↗
read the original abstract

Given graphs $H$ and $F$, the generalized Tur\'an number $\mathrm{ex}(n,H,F)$ is the maximum number of copies of $H$ among all $n$-vertex $F$-free graphs. The friendship graph $F_k$ consists of $k$ triangles sharing a common vertex. In this paper, we determine the value of $\mathrm{ex}(n,K_3,(t+1)F_k)$, where $K_3$ is a triangle, $t\geq 1$ is an integer, and $(t+1)F_k$ denotes a union of $(t+1)$ pairwise vertex-disjoint copies of $F_k$. Moreover, we characterize the extremal structure. Our result can be viewed as a generalization of the result of Zhu, Chen, Gerbner, Gy\H{o}ri, and Hama Karim, as well as of the remaining case left open by Wang, Ni, Liu, and Kang. In contrast to the extremal graphs of $F_k$, the extremal graphs of $(t+1)F_k$ undergo a fundamental change. This structure is also different from those of previous similar problems.

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 determines the exact value of the generalized Turán number ex(n, K_3, (t+1)F_k) for all integers t ≥ 1 and k ≥ 1, where F_k is the friendship graph consisting of k triangles sharing a vertex, and (t+1)F_k denotes t+1 vertex-disjoint copies. It also characterizes the extremal n-vertex graphs that maximize the number of triangles while remaining free of (t+1)F_k. The result is presented as a generalization of the single-F_k case settled by Zhu et al. and as resolving the remaining open case from Wang et al., with the key observation that the extremal construction undergoes a fundamental structural change when forbidding multiple disjoint copies.

Significance. If the exact determination and characterization hold, the paper supplies a complete solution to this family of generalized Turán problems. It identifies how the extremal graphs shift from the single-F_k regime to a new construction that remains optimal across all t ≥ 1 and all k, thereby extending the known results on ex(n, K_3, F) for friendship graphs and their disjoint unions. The work is grounded in combinatorial arguments without introducing fitted parameters or ad-hoc quantities.

major comments (1)
  1. [Main theorem and proof] The central claim that the new construction is optimal for every t ≥ 1 and every k rests on a full case analysis and stability argument whose details are not verifiable from the abstract alone; the load-bearing step is the verification that no other graph exceeds the stated bound in the regime where the structural change occurs (presumably §4 or the proof of the main theorem).
minor comments (2)
  1. [Introduction] The abstract states that the result 'can be viewed as a generalization' of Zhu et al. and the open case of Wang et al.; the introduction should include explicit statements of those prior theorems (with equation or theorem numbers) to make the precise improvement clear.
  2. [Abstract and §1] Notation for the forbidden graph is given as '(t+1)F_k' for the disjoint union; a brief sentence confirming that this is the standard vertex-disjoint union (rather than edge-disjoint) would remove any possible ambiguity for readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful review and for recognizing the paper as a complete solution to this family of generalized Turán problems. We address the single major comment below.

read point-by-point responses

  1. Referee: [Main theorem and proof] The central claim that the new construction is optimal for every t ≥ 1 and every k rests on a full case analysis and stability argument whose details are not verifiable from the abstract alone; the load-bearing step is the verification that no other graph exceeds the stated bound in the regime where the structural change occurs (presumably §4 or the proof of the main theorem).

    Authors: The complete proof, including the full case analysis and stability arguments, appears in Sections 3 and 4 of the manuscript (not the abstract). Section 3 establishes the upper bound via a stability lemma showing that any graph with more triangles than the proposed extremal construction must be structurally close to a blow-up of a complete bipartite graph augmented by a controlled number of triangles; this is proved by analyzing maximum-degree vertices, common-neighborhood counts, and triangle distributions. Section 4 then performs the case analysis for the regime of the structural change, verifying by exhaustive enumeration of possible edge and triangle configurations that exceeding the bound forces the appearance of (t+1) vertex-disjoint copies of F_k. The arguments are self-contained combinatorial arguments extending the single-copy techniques of Zhu et al. and the open case of Wang et al. All calculations and lemmas are written out explicitly, so the verification is available in the full text. We are happy to add a short proof outline to the introduction if the referee believes it would improve readability. revision: no

Circularity Check

0 steps flagged

No significant circularity; minor self-citation not load-bearing

full rationale

The derivation determines ex(n, K_3, (t+1)F_k) and characterizes the extremal graphs via direct combinatorial arguments that generalize prior independent results on F_k without reducing the extremal value to any fitted parameter, self-defined quantity, or ansatz imported from overlapping-author citations. The abstract and structure explicitly note a fundamental change from the single-F_k case, and the optimality claim rests on the new forbidden-subgraph analysis rather than on any equation or prior result that is equivalent to the target by construction. No load-bearing step collapses to a self-citation chain or renaming of known patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests only on standard graph-theoretic definitions and the usual extremal counting arguments; no ad-hoc constants or new objects are introduced.

axioms (1)
  • standard math Standard definitions of graphs, subgraphs, vertex-disjoint unions, and the generalized Turán function ex(n,H,F).
    Invoked throughout the statement and comparison with prior work.

pith-pipeline@v0.9.0 · 5508 in / 1159 out tokens · 43053 ms · 2026-05-08T16:12:22.694179+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

23 extracted references · 23 canonical work pages

  1. [1]

    H. L. Abbott, D. Hanson and H. Sauer, Intersection theorems for systems of sets, J. Combin. Theory Ser. A12(1972) 381-389

    work page 1972

  2. [2]

    Alon and C

    N. Alon and C. Shikhelman, ManyTcopies inH-free graphs,J. Combin. Theory Ser. B121(2016) 146-172

    work page 2016

  3. [3]

    Bollob´ as and E

    B. Bollob´ as and E. Gy˝ ori, Pentagons vs. triangles,Discrete Math.308(2008) 4332- 4336

    work page 2008

  4. [4]

    Chase, The maximum number of triangles in a graph of given maximum degree, Adv

    Z. Chase, The maximum number of triangles in a graph of given maximum degree, Adv. Comput.(2020) paper (10) 5

    work page 2020

  5. [5]

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

    work page 2003

  6. [6]

    G. Chen, X. Lei and S. Li, The exact Tur´ an number of disjoint graphs—a gen- eralization of Simonovits’ theorem, and beyond,European J. Combin.130(2025) 104226

    work page 2025

  7. [7]

    Chen, J.-B

    Y.-H. Chen, J.-B. Yang, L.-T. Yuan and P. Zhang, Exact generalized Tur´ an numbers for even linear forests,Discrete Math.347(2024) 113974

    work page 2024

  8. [8]

    Chv´ atal and D

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

    work page 1976

  9. [9]

    Erd˝ os, On some new inequalities concerning extremal properties of graphs, in: Theory of Graphs, Proceedings of the Colloquium Held at Tihany, 1966, pp

    P. Erd˝ os, On some new inequalities concerning extremal properties of graphs, in: Theory of Graphs, Proceedings of the Colloquium Held at Tihany, 1966, pp. 77-81

    work page 1966

  10. [10]

    Erd˝ os, On the number of complete subgraphs contained in certain graphs, Magy

    P. Erd˝ os, On the number of complete subgraphs contained in certain graphs, Magy. Tud. Akad. Mat. Kut. Int´ ez. K¨ ozl.7(1962) 459-464

    work page 1962

  11. [11]

    Erd˝ os, Some recent results on extremal problems in graph theory, in: Results, Theory of Graphs, International Symposium, Rome, 1966, 1967, pp

    P. Erd˝ os, Some recent results on extremal problems in graph theory, in: Results, Theory of Graphs, International Symposium, Rome, 1966, 1967, pp. 117-123

    work page 1966

  12. [12]

    Erd˝ os, Z

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

    work page 1995

  13. [13]

    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

    work page 1959

  14. [14]

    F¨ uredi and D.S

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

    work page 2015

  15. [15]

    Grzesik, On the maximum number of five-cycles in a triangle-free graph,J

    A. Grzesik, On the maximum number of five-cycles in a triangle-free graph,J. Combin. Theory Ser. B102(2012) 1061-1066

    work page 2012

  16. [16]

    Hatami, J

    H. Hatami, J. Hladk´ y, D. Kr´ al, S. Norine and A. Razborov, On the number of Pentagons in triangle-free graphs,J. Combin. Theory Ser. A120(2013) 722-732

    work page 2013

  17. [17]

    J. Hou, H. Li and Q. Zeng, Extremal graphs for the suspension of edge-critical graphs,Electron. J. Combin.31(4) (2024) P4.55

    work page 2024

  18. [18]

    Luo, The maximum number of cliques in graphs without long cycles,J

    R. Luo, The maximum number of cliques in graphs without long cycles,J. Combin. Theory, Ser. B128(2017) 219-226

    work page 2017

  19. [19]

    Simonovits, Extremal graph problems with symmetrical extremal graphs

    M. Simonovits, Extremal graph problems with symmetrical extremal graphs. Ad- ditional chromatic conditions,Discrete Math.7(1974) 349-376

    work page 1974

  20. [20]

    Tur´ an, On an extremal problem in graph theory (in Hungrarian),Mat

    P. Tur´ an, On an extremal problem in graph theory (in Hungrarian),Mat. es Fiz. Lapok.48(1941) 436-452

    work page 1941

  21. [21]

    Y. Wang, Z. Ni, Y. Liu and L. Kang, Generalized Tur´ an results for edge blow-up of star forests,Discrete Math.347(2024) 114149

    work page 2024

  22. [22]

    Yang and L.-T

    J.-B. Yang and L.-T. Yuan, A note on the stability results of the number of cliques in graphs with given matching number,Discrete Appl. Math.356(2024) 343-349

    work page 2024

  23. [23]

    X. Zhu, Y. Chen, D. Gerbner, E. Gy˝ ori and H. Hama Karim, The maximum number of triangles inF k-free graphs,European J. Combin.111(2023) 103793. 24

    work page 2023