Pith. sign in

REVIEW 4 major objections 4 minor 15 references

The generalized Tur\'an number for K_3 in graphs without suspensions of a path on five vertices

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

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

Pith's one-line read Graphs without a suspended five-vertex path have at most floor(n^2/8) triangles

desk verdict The exact k=5 case of the Mubayi–Mukherjee conjecture is settled with a stability proof; the result is likely correct, but Claim 3.6 misapplies Lemma 1 and several local structural claims are too compressed. read the letter →

arxiv 2509.03851 v1 pith:IBPUUBCS submitted 2025-09-04 math.CO

Doudou Hei , Xinmin Hou , Yue Ma This is my paper · ORCID
classification math.CO MSC 05C35
keywords generalizedTuránnumbertrianglecountsuspensionofapathP5-freestabilitymethodextremalgraphunique
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 settles the exact count of triangles in graphs that avoid the suspension of a five-vertex path—the graph made by adding one vertex adjacent to all vertices of a path on five vertices. It proves that for every sufficiently large n, the maximum number of triangles in such an n-vertex graph is floor(n^2/8), and that the only graph achieving this maximum is H_n, an almost balanced complete bipartite graph with a perfect matching inserted into one part. This makes the k=5 case of the conjecture from [10] exact rather than merely asymptotic, and it is one of the few stability proofs for generalized Turán numbers where the forbidden graph and the counted graph have the same chromatic number. The lower bound is easy—H_n itself has floor(n^2/8) triangles and no suspended P5—so the work lies in the upper bound and the structural uniqueness.

What carries the argument

The mechanism is the stability method combined with a three-part triangle classification. The proof partitions a near-extremal graph into two large parts V1 and A2 and two negligible parts B1 and B2, classifies every triangle by how many vertices lie in each part, and repeatedly applies local adjustments: if a nonempty component remains in B1 or B2, the proof rewires that component into complete bipartite adjacency plus a perfect matching. Each adjustment is claimed to preserve hat-P5-freeness while strictly increasing the triangle count, contradicting maximality. The engine is the dichotomy that vertices in B1 have small triangle count unless the structure collapses, and a lemma bounding tr

What would settle it

Take n divisible by 4 and search all graphs within edit distance o(n^2) of K_{n/2,n/2} that are hat-P5-free; the theorem predicts a strict maximum of n^2/8 triangles. Any such graph with more than n^2/8 triangles refutes Theorem 1.4. Equivalently, an explicit bound on the hidden o(n) term in the imported edge-density theorem would settle the threshold at which the stability argument becomes valid, since that threshold is the only non-effective step.

Watch

Extended reading notes

Core claim

Let hat P5 denote the suspension of a path on five vertices. The central claim, Theorem 1.4, is that ex(n,K3,hat P5)=floor(n^2/8) for all sufficiently large n, with H_n as the unique extremal graph. H_n is built from a balanced complete bipartite graph by adding a perfect matching inside one of the two parts. The proof starts from a theorem of [10] saying that any hat-P5-free graph with nearly floor(n^2/8) triangles has nearly n^2/4 edges, applies a standard stability theorem to conclude the graph is close to a complete bipartite graph, and then uses a chain of claims about neighborhoods of vertices in the small correcting parts to force them to be empty. Once the two small parts disappear,

Load-bearing premise

The proof depends on two quoted bounds it does not prove: a hat-P5-free graph with near-maximum triangles must have near n^2/4 edges, and ex(n,hat P5) is at most n^2/4+O(n); if either is wrong by more than its stated error, the stability argument cannot begin.

Editorial extensions

If this is right

  • The exact maximum for k=5 is floor(n^2/8), and the extremal graph is unique for sufficiently large n.
  • The proof gives a template for same-chromatic generalized Turán problems, where the forbidden graph and the counted graph both have chromatic number 3.
  • For k=6 and beyond, Construction 3 in the paper gives a lower bound strictly larger than the original construction, so the original lower-bound construction is not the right extremal family for k≥6.
  • The asymptotic form of the conjecture for k=5 is confirmed; the exact k=4 case is already known, leaving k≥6 open.

Reading between the lines

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

  • If the same stability strategy is run for k=6 with the improved lower-bound construction, the extremal graph may have triangles inside the large part rather than only cross-part triangles; a likely consequence is that the conjectured extremal structure changes with k.
  • The proof's finite list of forbidden local configurations, such as two adjacent vertices in B1 with too many common A2-neighbors, could be turned into an automated check for small n, giving an independently verifiable threshold.
  • The size of the sufficient n depends on the o(n) terms in the imported bounds from [10] and [15]; making those bounds explicit would yield an actual numerical threshold instead of 'sufficiently large'.
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.

Referee Report

4 major / 4 minor

Summary. The paper studies ex(n,K3,hat P5), the maximum number of triangles in an n-vertex graph containing no suspension of a path on five vertices. The main result, Theorem 1.4, asserts that for all sufficiently large n this maximum is floor(n^2/8), and that the unique extremal graph is H_n, the balanced complete bipartite graph with a perfect matching added in one part. The proof is by the stability method: Theorem 2.1 supplies a lower bound on the number of edges in a triangle-dense hat-P5-free graph; the Erdos-Simonovits stability theorem then gives an approximate bipartition; a sequence of structural claims (Claims 3.1 to 3.6) forces the exceptional sets to be empty; and a final calculation identifies H_n as the unique extremal graph.

Significance. If the proof is correct, this is a significant result: it settles the exact k=5 case of the Mubayi-Mukherjee conjecture and identifies the unique extremal structure. It is also methodologically interesting because it uses stability in a setting where chi(F)=chi(H)=3, unlike many earlier generalized Turan stability arguments. The lower-bound construction H_n is simple and natural. However, the proof as written relies on heavy imported inputs and compresses several local structural arguments; the main theorem is not yet fully verified by the text. The paper is a plausible and important contribution, but it needs a careful repair before it can be accepted.

major comments (4)
  1. [Section 2, Theorem 2.1] Theorem 2.1 is stated as 'can be indirectly derived from the proof of Theorem 1.4 for k=4 in [10]', but no derivation is given and no exact statement in [10] is cited. This theorem is load-bearing: at the start of Section 3 it is used to get e(G) >= n^2/4 - o(n^2), which is the precondition for applying the Erdos-Simonovits stability theorem. Since G is hat-P5-free rather than hat-P4-free, the implication is not immediate from the k=4 result in [10]. The authors should either prove Theorem 2.1 in full or give a precise reference to a stated and proved theorem that implies it.
  2. [Section 3, Claim 3.4] In the proof of the odd case, after choosing v,w in N_H(u), the authors derive N2(u) cap N2(v) cap N2(w) = empty and then state: 'Namely, any vertex in N2(u) is adjacent to at most one vertex of N1(u).' This global statement does not follow: the preceding argument only applies to neighbors v,w inside the selected set K, not to all vertices in N1(u). The subsequent displayed inequalities sum over all x in N1(u), so the proof needs an argument covering all neighbors of u, not just those in H. There is also a persistent confusion in this claim between t(H), the number of triangles containing a vertex of H, and t'(H), the auxiliary count defined in the claim. This claim is used directly in the adjustment argument for B1, so it is load-bearing.
  3. [Section 3, Claim 3.6] The application of Lemma 1 is not justified as written. Lemma 1 requires a partition V1 union A2 with |A2| = o(|V1|), but at this stage the graph has a large independent set A2 of size Theta(n). The sentence 'By Lemma 1, before adjustment, t(B2) < |B2|*|V1|/2' cannot be read as applying Lemma 1 to the whole graph. The intended argument must be to apply Lemma 1 to the induced subgraph on V1 union B2, using the previously established absence of edges between A2 and B2 and the fact that every vertex of B2 has r(w) = Omega(n). This is not stated, and the notation (with A2 used both for the large part and for the small exceptional set) makes it unreadable. The strict inequality is essential for the claimed contradiction, so this needs a clear and correct derivation.
  4. [Section 3, Claims 3.5 and 3.6] The adjustment operations are asserted to preserve hat-P5-freeness with 'Obviously, after this adjustment, no new copy of hat P5 will be created.' Since the contradiction relies on producing a hat-P5-free graph with more triangles, this preservation must be proved. The operations add many edges: in Claim 3.5, complete bipartite connections from a moved vertex and from a matching inside B1 to A2, and in Claim 3.6, all edges between B2 and V1. These are substantial changes, and the hat-P5-free property is delicate. The proof should include a case analysis of potential hat-P5 subgraphs after the adjustment, or at least a precise reduction showing that any new hat P5 would force one before the adjustment.
minor comments (4)
  1. [Section 3, notation] The parts of the extremal complete bipartite graph are first called V1 and A2, but later the proof uses V1 and V2 with subsets A_i and B_i. The line '|Vi|=|A2|-o(n), for i=1,2' is not meaningful as written. Please adopt a consistent notation, e.g. V1,V2 for the two large parts and A_i,B_i for their subsets.
  2. [Section 3, Claim 3.2] In the paragraph after Claim 3.2, 'let D1 be the common neighborhood of g,h in A1, then |D1|=|A2|-o(n)' should presumably read |A1|-o(n). Such size typos make the argument hard to verify.
  3. [Section 3, Claims 3.3 and 3.4] The proof of Claim 3.3 uses induction on d1(u) and in Cases 1 and 2 deletes sets of vertices, but it is not always clear whether the current graph or the original graph is meant by G and by the N_i notation. Please clarify the induction setup.
  4. [General] There are several typographical errors: 'probelm', 'Frist', 'tirangles', 'Mukheherjee', and inconsistent use of 'hat P5' versus 'widehat'. These should be corrected in a revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is a stability argument using external theorems; no fitted quantity is relabeled as a prediction.

full rationale

The paper's central claim (Theorem 1.4) is an exact extremal value. The derivation chain is: (1) lower bound from an explicit graph Hn that is checked directly to be hat P5-free and to contain floor(n^2/8) triangles; (2) an edge-density lower bound e(G) >= n^2/4 - o(n^2) imported as Theorem 2.1 from Mubayi-Mukherjee [10]; (3) an upper bound ex(n,hat P5) <= n^2/4 + O(n) imported as the Corollary of Theorem 2.3 from Zhu-Wang-Zhang-Zhang [15]; (4) Erdős-Simonovits stability to force near-bipartiteness; and (5) a sequence of structural claims (3.1-3.6) that eliminate the small error sets and identify the extremal graph as Hn. None of these steps fits a parameter to the target quantity and then re-predicts it. Theorem 2.1 is a distinct auxiliary bound (a lower bound on edges given many triangles), not a restatement of ex(n,K3,hat P5); Theorem 2.3 is a Turán-number bound for hat P5, not the generalized Turán number for K3. Both are by authors other than the present ones, so there is no self-citation chain. The lower-bound construction is externally verified. The internal claims are structural; even the potentially questionable use of Lemma 1 in Claim 3.6 (where the lemma's partition hypothesis may not match the full graph containing the large stable set A2) would be a proof gap or an error in application, not circularity, because Lemma 1 is an independent auxiliary statement and the bound is not being assumed as the conclusion. No equation is defined in terms of the theorem it is used to prove, and no 'prediction' is produced from fitted inputs. Therefore the paper does not exhibit circular reasoning.

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

The proof introduces no fitted constants and no new objects. It rests on standard extremal graph theory tools plus two imported bounds: one described as indirectly derivable from [10], and one depending on the arXiv preprint [15]. The adjustment operations in the structural characterization are asserted without full verification.

assumptions (5)
  • standard math Erdős-Gallai theorem: ex(n,P_k) <= (k-2)n/2
    Used in Section 2 and in deriving d(x)>= (n-6)/6 from t(x)>= (n-6)/4.
  • standard math Erdős-Simonovits stability theorem: F-free graph with near-extremal edge count is close to Turán graph T(n,chi(F)-1)
    Central tool in Section 3 to force near-bipartiteness of extremal G.
  • domain assumption Theorem 2.3 from [15]: ex(n,hat T) <= f(n,k) for balanced trees T under Erdős-Sós; corollary ex(n,hat P5) <= n^2/4 + floor((n+1)/4)
    Imported from an arXiv preprint; used with stability to control missing edges from the complete bipartite graph.
  • domain assumption Theorem 2.1 from [10]: if G is P5-hat-free and t(G)>= n^2/8-o(n^2) then e(G)>= n^2/4-o(n^2)
    Imported, described as indirectly derivable from [10]; supplies the edge density needed to start stability.
  • ad hoc to paper The structural adjustment operations in Claims 3.5 and 3.6 do not create a new P5-hat subgraph
    Asserted with 'obviously'; if false, the extremal contradiction fails.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The generalized Tur\'an number for K_3 in graphs without suspensions of a path on five vertices." pith.science (2026). https://pith.science/paper/IBPUUBCS

@misc{pith2026250903851,
  author       = {Pith},
  title        = {Pith review of: The generalized Tur\'an number for K_3 in graphs without suspensions of a path on five vertices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IBPUUBCS}},
  note         = {Machine review of arXiv:2509.03851}
}
abstract

Given graphs $H$ and $F$, the generalized Tur\'an number $\ex(n, H, F)$ is defined as the maximum number of copies of $H$ in an $n$-vertex graph that contains no copy of $F$. The suspension $\widehat{F}$ of a graph $F$ is obtained by adding a new vertex that is adjacent to every vertex of $F$. Mubayi and Mukherjee (2023, DM) conjectured that $\ex(n, K_3, \widehat{P_k})=\left\lfloor \frac{k-2}{2}\right\rfloor \cdot \frac{n^2}{8}+o(n^2)$, where $P_k$ is a path on $k\ge 4$ vertices. Using the triangle removal lemma, they verified this conjecture for $k=4,5,6$. Later, Mukherjee (2024, DM) established the exact value $\ex(n, K_3, \widehat{P_4})=\left\lfloor n^2/8\right\rfloor$. In this paper, using the stability method, we determine the exact value of $\ex(n, K_3, \widehat{P_5})$ by showing that for sufficiently large $n$, $\ex(n,K_3, \widehat{P_5})=\left\lfloor n^2/8\right\rfloor.$

Figures

Figures reproduced from arXiv: 2509.03851 by the authors.

Figure 1
Figure 1. Structure of G Case 1: There exist two vertices x and y in N1(u) such that |N2(u) ∩ N2(x) ∩ N2(y)| = 2. Then neither x nor y can have other neighbors in N2(u). Let {x ′ , y′} = N2(u) ∩ N2(x) ∩ N2(y). For any vertex z ∈ N1(u) \ {x, y}, we have zx′ , zy′ ∈/ E(G), since G is Pc5-free. Let G′ = G−{x, y, x′ , y′}. By the induction hypothesis on u in G′ , we have t1(u) − t(xu) − t(yu) ≤ d2(u) − 2 + o(n). Combining with t(… view at source ↗
Figure 2
Figure 2. Structure between N1(u) and N2(u) words, any vertex in N2(u) is adjacent to at most one vertex of N1(u) (as shown in [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Structural adjustment diagram while let the remaining 2k vertices in H form a perfect matching consisting of k edges by pairing them into k disjoint pairs. And make each vertex of the 2k vertices adjacent to all vertices in A2. Obviously, after this adjustment, no new copy of Pc5 will be created. By Claim 3.4, before adjustment, t(H) ≤ k · |A2| + o(n). After adjustment, t(H) = n 4 − o(n) + k · |A2|, since there are … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 14 canonical work pages

  1. [10]

    Mubayi and S

    D. Mubayi and S. Mukherjee. Triangles in graphs without bipartite sus- pensions. Discrete Mathematics, 346(6):113355, 2023

    work page 2023

  2. [1]

    Alon and C

    N. Alon and C. Shikhelman. Many T copies in H-free graphs. J. Combin. Theory Ser. B , 121:146–172, 2016. 13

    work page 2016

  3. [2]

    Bollob´ as and E

    B. Bollob´ as and E. Gy˝ ori. Pentagons vs. triangles.Discrete Mathematics, 308(19):4332–4336, 2008

    work page 2008

  4. [3]

    P. Erd˝ os. Problems and results in combinatorial analysis and graph theory. Annals of Discrete Mathematics , 38:81–92, 1988

    work page 1988

  5. [4]

    Erd˝ os and T

    P. Erd˝ os and T. Gallai. On maximal paths and circuits of graphs. Acta Mathematica Academiae Scientiarum Hungarica, 10:337–359, 1959

    work page 1959

  6. [5]

    D. Gerbner. A note on the number of triangles in graphs without the suspension of a path on four vertices. Discrete Mathematics Letters, 10:32– 34, 2022

    work page 2022

  7. [6]

    D. Gerbner. Generalized Tur´ an problems for small graphs. Discussiones Mathematicae Graph Theory, 43:549–572, 2023

    work page 2023

  8. [7]

    D. Gerbner. Some stability and exact results in generalized Tur´ an problems. Studia Scientiarum Mathematicarum Hungarica , 60(1):16–26, 2023

    work page 2023

Show all 15 references
  1. [8]

    Gerbner and C

    D. Gerbner and C. Palmer. Survey of generalized Tur´ an problems— count- ing Subgraphs. arXiv preprint. arXiv:2506.03418 , 2025

    2025 arXiv

  2. [9]

    Gy˝ ori and H

    E. Gy˝ ori and H. Li. The maximum number of triangles inC2k+1-free graphs. Combinatorics, Probability and Computing , 21(1-2):187–191, 2012

    2012

  3. [11]

    Mukherjee

    S. Mukherjee. Exact generalized Tur´ an number for K3 versus suspension of P4. Discrete Mathematics, 347(4):113866, 2024

    2024

  4. [12]

    Simonovits

    M. Simonovits. A method for solving extremal problems in graph theory, stability problems. Theory of Graphs (Proc. Colloq., Tihany, 1966) , pages 279–319, 1968

    1966

  5. [13]

    Yuan and Y

    X. Yuan and Y. Peng. On generalized Tur´ an numbers of intersecting cliques. Graphs and Combinatorics , 41(1):1–13, 2025

    2025

  6. [14]

    X. Zhu, Y. Chen, D. Gerbner, E. Gy˝ ori, and H. Hama Karim. The maxi- mum number of triangles in Fk-free graphs. European Journal of Combi- natorics, 114:103793, 2023

    2023

  7. [15]

    X. Zhu, X. Wang, Y. Zhang, and F. Zhang. Tur´ an problems for suspension of a balanced tree. arXiv preprint. arXiv:2503.05166 , 2025. 14

    2025 arXiv

Pith tools

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