pith. sign in

arxiv: 2605.17430 · v1 · pith:GDVBDKAZnew · submitted 2026-05-17 · 🧮 math.CO

Triangles in graphs without the expansion of 4-cycle

Jialei Song , Qi Wu , Long-Tu Yuan This is my paper

Pith reviewed 2026-05-19 22:52 UTC · model grok-4.3

classification 🧮 math.CO
keywords extremal graph theorytriangle countingforbidden subgraphsgraph expansioncycle expansionpath expansioncounterexamples
0
0 comments X

The pith

The expansion of the 4-cycle is the only counterexample to a conjecture on the maximum number of triangles in graphs avoiding expanded paths and cycles.

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

A conjecture stated the largest possible number of triangles in a graph free of the expansions of paths or cycles of length at least 4. Earlier results settled the conjecture for all expanded paths of length 4 or more and for expanded cycles of length 5 or more. This work handles the last open case by proving that graphs without the expansion of the 4-cycle can contain more triangles than the conjectured limit, making this the single exception. A sympathetic reader cares because the result finishes the classification of these extremal problems and identifies exactly where the proposed bound fails to be tight.

Core claim

The paper shows that the conjectured upper bound on the number of triangles holds in graphs that avoid the expansion of any path of length at least 4 or any cycle of length at least 5, but fails when the forbidden structure is the expansion of the 4-cycle; the latter is therefore the unique counterexample among all the cases considered.

What carries the argument

The expansion F^Δ of a graph F, formed by replacing each edge of F with a triangle, serving as the forbidden subgraph whose avoidance controls the maximum triangle count.

Load-bearing premise

The conjecture is correct for the expansions of all paths of length at least 4 and all cycles of length at least 5.

What would settle it

A graph that avoids the expansion of the 4-cycle yet contains strictly fewer triangles than the largest number achieved by any such graph, or an additional expanded path or cycle that also exceeds the conjectured bound.

Figures

Figures reproduced from arXiv: 2605.17430 by Jialei Song, Long-tu Yuan, Qi Wu.

Figure 1
Figure 1. Figure 1: The graph C △ 4 and the graph S =(n). denote the number of edges between X and Y . Choose v ∈ V (G), we define links of v in X by LX(v) := {e ∈ E(G[X]): there exists a triangle composed by v and e in G}, and for an edge e ∈ E(G[X]), N ∗ X(e) := {u ∈ X \ V (e): there exists a triangle in G containing both e and u} as co-neighborhood of e in X. Moreover, let dX(e) = |N∗ X(e)|. We characterize F as a 2-inters… view at source ↗
read the original abstract

The expansion $F^{\triangle}$ of a graph $F$ is the graph obtained from $F$ by replacing each edge with a triangle. Lv \etal proposed a conjecture on the maximum number of triangles in a graph without $P_k^{\triangle}$ or $C_k^{\triangle}$ for every $k \ge 4$. Their conjecture was confirmed in previous work for $P_k^{\triangle}$ when $k \ge 4$ and $C_k^{\triangle}$ when $k \ge 5$. In this note, we resolve the remaining case $C_4^{\triangle}$, demonstrating that this is the only counterexample to their conjecture.

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

2 major / 2 minor

Summary. The manuscript resolves the final open case of the Lv et al. conjecture on the maximum number of triangles in graphs forbidding the triangle-expansion F^Δ. It treats the case F = C_4, proves the extremal bound for C_4^Δ-free graphs, and concludes that C_4^Δ is the unique counterexample among all P_k^Δ (k ≥ 4) and C_k^Δ (k ≥ 5).

Significance. If the new C_4^Δ analysis is correct, the note completes the verification of the conjecture, giving a clean classification of the extremal function ex(n, F^Δ, K_3) for all paths and cycles of length at least 4. The work relies on the standard definition of F^Δ and on previously established cases; its value lies in closing the last gap rather than in introducing new machinery.

major comments (2)
  1. [§2] §2 (main theorem statement): the claim that C_4^Δ is the 'only counterexample' rests on the validity of the cited results for P_k^Δ (k≥4) and C_k^Δ (k≥5). A short paragraph summarizing the precise bounds obtained in those papers would make the 'only' qualifier self-contained and easier to verify.
  2. [§3] §3 (proof of the C_4^Δ bound): the triangle-counting argument appears to use the standard edge-triangle incidence counting; confirm that the extremal construction achieving the bound is explicitly exhibited and that no larger construction is possible under the C_4^Δ-free condition.
minor comments (2)
  1. [Introduction] Notation: ensure that the expansion operator ^Δ is defined at first use and that the conjecture statement is restated verbatim before the new result is announced.
  2. [References] References: add the full bibliographic details for the prior papers on P_k^Δ and C_k^Δ so that readers can locate the exact statements being invoked.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the referee's positive evaluation and helpful suggestions. We respond to the major comments below.

read point-by-point responses

  1. Referee: [§2] §2 (main theorem statement): the claim that C_4^Δ is the 'only counterexample' rests on the validity of the cited results for P_k^Δ (k≥4) and C_k^Δ (k≥5). A short paragraph summarizing the precise bounds obtained in those papers would make the 'only' qualifier self-contained and easier to verify.

    Authors: We agree that this would improve the readability. In the revised manuscript, we will insert a short paragraph in §2 that recalls the precise extremal bounds from the cited papers on P_k^Δ and C_k^Δ (k≥5). This will make the uniqueness claim self-contained without requiring the reader to consult the references for the exact statements. revision: yes

  2. Referee: [§3] §3 (proof of the C_4^Δ bound): the triangle-counting argument appears to use the standard edge-triangle incidence counting; confirm that the extremal construction achieving the bound is explicitly exhibited and that no larger construction is possible under the C_4^Δ-free condition.

    Authors: The extremal construction is explicitly exhibited in §3 of the manuscript. The proof uses standard edge-triangle incidence counting to establish the upper bound on the number of triangles in a C_4^Δ-free graph. We show that the exhibited construction achieves this bound and that the counting argument implies no C_4^Δ-free graph can have more triangles. revision: no

Circularity Check

0 steps flagged

No circularity; new case resolved independently with external priors

full rationale

The paper's core contribution is a direct resolution of the C_4^Δ case via a new argument establishing the triangle bound in C_4^Δ-free graphs. The claim that this is the sole counterexample to the Lv et al. conjecture is assembled by combining the new result with separately cited prior confirmations for all other cases (P_k^Δ k≥4 and C_k^Δ k≥5). No equations or definitions in the note reduce the new bound to a fit or to a self-referential construction; the priors are treated as external literature results rather than re-derived or self-cited load-bearing steps within this manuscript. This is standard mathematical practice and does not constitute circularity under the specified criteria.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger is limited to the explicit definition given there. No free parameters, invented entities, or non-standard axioms are identifiable from the provided text.

axioms (1)
  • standard math The expansion F^Δ of a graph F is obtained by replacing each edge with a triangle.
    This is the central definition used to state the conjecture and the new result.

pith-pipeline@v0.9.0 · 5634 in / 1094 out tokens · 48446 ms · 2026-05-19T22:52:34.479223+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

  1. [1]

    Alon and C

    N. Alon and C. Shikhelman. ManyTcopies inH-free graphs.J. Combin. Theory Ser. B, 121:146–172, 2016. 2

    work page 2016

  2. [2]

    P. Erd˝ os. On the number of complete subgraphs contained in certain graphs.Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl., 7:459–464, 1962. 2

    work page 1962

  3. [3]

    Gerbner and B

    D. Gerbner and B. Patk´ os. Generalized Tur´ an results for intersecting cliques.Discrete Math., 347(1):113710, 2024. 2

    work page 2024

  4. [4]

    Kostochka, D

    A. Kostochka, D. Mubayi, and J. Verstra¨ ete. Tur´ an problems and shadows I: Paths and cycles.J. Combin. Theory Ser. A, 129:57–79, 2015. 2, 3

    work page 2015

  5. [5]

    Kostochka, D

    A. Kostochka, D. Mubayi, and J. Verstra¨ ete. Tur´ an problems and shadows II: Trees. J. Combin. Theory Ser. B, 122:457–478, 2017. 2 8

    work page 2017

  6. [6]

    X. Liu, J. Song, and L.-T. Yuan. Exact results for some extremal problems on expansions I.Communications in Mathematics and Statistics, online first, 1–38, 2025. doi:10.1007/s40304-024-00429-y. 2, 3, 4, 5, 6

    work page doi:10.1007/s40304-024-00429-y 2025

  7. [7]

    Z. Lv, E. Gy˝ ori, Z. He, N. Salia, C. Tompkins, K. Varga, and X. Zhu. Generalized Tur´ an numbers for the edge blow-up of a graph.Discrete Math., 347(1):113682, 2024. 2

    work page 2024

  8. [8]

    P. Tur´ an. On an extremal problem in graph theory.Mat. Fiz. Lapok, 48:436–452,

    work page

  9. [9]

    Yuan and W

    X. Yuan and W. Yang. On generalized Tur´ an number of two disjoint cliques.Graphs Combin., 38:116, 2022. 2

    work page 2022

  10. [10]

    X. Zhu, Y. Chen, D. Gerbner, E. Gy˝ ori, and H. H. Karim. The maximum number of triangles inF k-free graphs.European J. Combin., 114:103793, 2023. 2

    work page 2023

  11. [11]

    A. A. Zykov. On some properties of linear complexes.Mat. Sb. (N.S.), 24(66), no. 2, 163–188, 1949. 1 9

    work page 1949