Pith. sign in

REVIEW 4 minor 7 references

Clique-saturating non-edges throughout the Tur\'an range

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

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

Pith's one-line read For every $p\ge 3$, the minimum number of $K_{p+1}$-saturating non-edges is $\Phi_p(\lambda)n^2+O_p(n)$ for every $m$ between $t_{p-1}(n)$ and $t_p(n)$, and the triangle case is exact.

desk verdict Answers the full He-Ma-Ma-Ye question for clique-saturating non-edges, with a clean asymptotic formula and a new exact triangle result; the proof is intricate but checks out. read the letter →

arxiv 2608.25831 v1 pith:N3AWTETL submitted 2026-08-26 math.CO

Xiaolin Wang , Jiabao Yang , Ruilin Zheng This is my paper · ORCID
classification math.CO MSC 05C3505C70
keywords clique-saturatingnon-edgesTuránnumbersaturationextremalgraphtheoryK_p-freegraphsK_p-packingtriangle-freeasymptoticformula
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, up to lower-order error, the minimum number of $K_{p+1}$-saturating non-edges in a $K_{p+1}$-free graph with a prescribed number of edges, for every fixed $p\ge 3$ and every edge count $m$ between the two thresholds $t_{p-1}(n)$ and $t_p(n)$. The answer is a single continuous profile $\Phi_p(\lambda)n^2+O_p(n)$, where $\lambda$ is the relative position of $m$ inside that interval and $\Phi_p$ is defined through the positive root of a quartic polynomial. At the lower endpoint the profile reproduces the earlier asymptotic found one edge above $t_{p-1}(n)$; at the upper endpoint it counts all non-edges of the balanced complete $p$-partite graph. The paper also gives an exact formula, expressed as a finite partition optimization, for the triangle case $p=2$. A sympathetic reader should care because this converts a hard extremal endpoint question into a complete answer over the whole edge-density range.

What carries the argument

The lower bound is carried by a maximum $K_p$-packing $\mathcal R$, chosen among maximum packings to maximize $e(G-V(\mathcal R))$. A switching lemma shows that after relabeling, one clique of the packing has an empty common-neighborhood class while retaining at least the averaged number of edges to the remaining graph. This lets the saturating non-edges be split into two disjoint groups: those incident to the packed vertices, bounded below by an edge-counting inequality, and those inside the remaining $K_p$-free graph $H$, bounded below by convexity from the size $z$ of the surviving common-neighborhood classes. Both estimates are functions of the packing density $r=|R|/n$, and the whole bound reduces to minimizing one explicit function $F_\alpha(r)$ on $(0,1/p]$; its unique minimizer is exactly $x_p(\lambda)$, giving $\Phi_p(\lambda)$. The matching upper bound uses a blow-up construction whose vertex classes $V_0,V_1,\dots,V_{p-1},U_1,\dots,U_{p-1}$ have carefully chosen edge patterns; its edge count and its count of saturating non-edges are both quadratic forms in the class sizes, and the definitions of $x_p$ and $y_p$ make those forms agree with $\Phi_p$.

What would settle it

For $p=3$, solve the exact minimization over all $K_4$-free graphs on $n=12$ vertices with $m$ edges by exhaustive branch-and-bound; if the observed minimum differs from $\Phi_3(\lambda)n^2+O(n)$ by more than a small constant for some $\lambda$, the asymptotic statement fails. For $p=2$, compute Theorem 1.5's dynamic program and verify it against brute-force enumeration of triangle-free graphs with $n\le 12$; any mismatch would disprove Theorem 1.4.

Watch

Extended reading notes

Core claim

For every fixed $p\ge 3$, set $\lambda=(m-t_{p-1}(n))/(t_p(n)-t_{p-1}(n))$ for $t_{p-1}(n)<m\le t_p(n)$, let $x_p(\lambda)$ be the unique positive root of $p^3D_px^4-2p^2(p-2)^2x^3-2p(p-2)\lambda x-\lambda^2=0$, with $D_p=4p^2-11p+8$, and define $y_p(\lambda)=\lambda/(2p(p-1)x_p(\lambda))+(p-2)/(p-1)(1-x_p(\lambda)/2)$ and $\Phi_p(\lambda)=\frac12(x_p(\lambda)^2+y_p(\lambda)^2/(p-1))$. The paper proves $f_{p+1}(n,m)=\Phi_p(\lambda)n^2+O_p(n)$ uniformly over the whole interval. The same formula interpolates the known endpoints: as $\lambda\to0^+$ it gives $2(p-2)^2/[p(4p^2-11p+8)]$, and at $\lambda=1$ it gives $1/(2p)$, which equals the proportion of non-edges in $T_p(n)$. For $p=2$, the paper proves that $f_3(n,m)$ equals the minimum of $\sum_i s(q_i)$ over partitions $\sum_i q_i=n$ with $\sum_i t(q_i)\ge m$, where $t(q)=\lfloor q^2/4\rfloor$ and $s(q)=\lfloor(q-1)^2/4\rfloor$.

Load-bearing premise

The load-bearing premise is the switching lemma for the chosen maximum $K_p$-packing: it asserts that one can rearrange the packing so that some clique has an empty common-neighborhood class while still meeting the averaged edge lower bound, and the proof of Theorem 1.3 collapses if no such relabeling can be guaranteed.

Editorial extensions

If this is right

  • The full asymptotic profile for $f_{p+1}(n,m)$ is now known on the entire interval $t_{p-1}(n)<m\le t_p(n)$, so the endpoint results are special cases of one formula.
  • At $m=t_p(n)$, the formula reproduces the fact that every non-edge of the complete $p$-partite Turán graph is saturating, so the result is consistent with the extremal edge count.
  • For any fixed $p$, the function $\Phi_p(\lambda)$ gives a concrete numerical prediction that can be checked by computer for large $n$ and many values of $\lambda$.
  • For triangle-free graphs, $f_3(n,m)$ is computable exactly by the dynamic program in Theorem 1.5, so the same function can be tabulated and compared with constructions.

Reading between the lines

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

  • A natural next step, not taken in the paper, is a stability theorem: if a graph's saturating non-edge count is close to $\Phi_p(\lambda)n^2$, the graph should be close to the blow-up construction, since the lower-bound proof has a unique minimizer $r=x_p(\lambda)$.
  • The one-variable reduction suggests the same packing-plus-switching method might apply to other forbidden subgraphs whose common-neighborhood structure is clique-like, producing analogous profiles between consecutive thresholds.
  • For $p=2$, the exact partition formula may have a simpler piecewise-linear or closed form in terms of the largest part; the dynamic program could be used to detect such structure for small $n$.
Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: For every fixed $p\ge 3$, set $\lambda=(m-t_{p-1}(n))/(t_p(n)-t_{p-1}(n))$ for $t_{p-1}(n)<m\le t_p(n)$, let $x_p(\lambda)$ be the unique positive root of $p^3D_px^4-2p^2(p-2)^2x^3-2p(p-2)\lambda x-\lambda^2=0$, with $D_p=4p^2-11p+8$, and define $y_p(\lambda)=\lambda/(2p(p-1)x_p(\lambda))+(p-2)/(p-1)(1-x_p(\lambda)/2)$ and $\Phi_p(\lambda)=\frac12(x_p(\lambda)^2+y_p(\lambda)^2/(p-1))$. The paper p

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies f_{p+1}(n,m), the minimum number of K_{p+1}-saturating non-edges in an n-vertex K_{p+1}-free graph with m edges. For every fixed p≥3 and every m in the interval t_{p-1}(n)<m≤t_p(n), Theorem 1.3 gives an asymptotic formula Φ_p(λ)n^2+O_p(n), where λ is the normalized excess over t_{p-1}(n) and Φ_p is defined from the unique positive root of the quartic (2). The upper bound is by an explicit blow-up construction, and the lower bound uses a maximum K_p-packing, a switching lemma, and a one-variable minimization. Theorem 1.4 gives an exact finite-optimization formula for f_3(n,m) for all 0≤m≤t_2(n), and Theorem 1.5 gives a dynamic-programming recurrence for it. The paper also checks the endpoint values against earlier results of Balogh and Liu and of He, Ma, Ma, and Ye.

Significance. If correct, the paper fully answers the question posed in [7] for K_{p+1}-saturating non-edges throughout the Turán range, extending the endpoint result of Theorem 1.2 to a parameter-free profile Φ_p(λ). The formula is genuinely derived rather than fitted: the polynomial in (2) comes from minimizing the lower-bound function F_α(r) in Lemma 3.4, and at λ=0 and λ=1 it reproduces the known extremal constants. I checked the algebraic identities (8), the endpoint evaluations, the packing lower bounds (11)-(15), the optimization in Lemma 3.4, and the induction in Lemma 4.4; the arguments are coherent and no circular use of the main result occurs. The exact formula for f_3(n,m) is a welcome additional contribution. The paper is explicit enough that the computations can be verified line by line.

minor comments (4)
  1. [§3, Lemma 3.1] The displayed difference in the proof is correct, but the cancellation is terse: the terms e(R\X,X) and e(R\X,Y) are equal because X and Y are cliques with |X|=|Y|. Adding this one-line explanation would prevent the misreading that a term is missing.
  2. [§4, Lemma 4.2] The sentence "since G is triangle-free, N_G(v) and N_2(v) are both independent" is misleading: N_2(v) is not independent in an arbitrary triangle-free graph, and the argument uses the previously established fact that every vertex of N_2(v) is adjacent to every vertex of N_G(v). Please rephrase to state the needed reason.
  3. [§3, Proposition 3.3] In the passage from (13) to (15), the justification that z^2 ≥ (α/r+a−br)_+^2 − O_p(n^{-1}) is compressed; since the right-hand side can in principle exceed 1 for small r, it would help to note explicitly that (13) combined with z≤1 rules out such r, or to state that the display is only needed when the bracket lies in [0,1].
  4. [§2, Lemma 2.1] The proof of the bound x≤1/p for λ=0 is handled by a separate direct check, but the display Q_λ(√(λ/p)) contains the expression 1/√λ; please make the λ=0 case fully explicit so that the displayed formula is not evaluated there.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1.3 and Theorem 1.4 are derived, not assumed.

full rationale

The derivation chain for Theorem 1.3 is self-contained. The upper-bound construction is a concrete blow-up graph whose edge count is verified by equation (8); this verification uses the definitions of x and y from (3), but it is a construction rather than a fit, and the same quantities are later forced from below by the independent minimization in Lemma 3.4. The lower bound does not assume the desired formula: it starts from a maximum Kp-packing chosen to maximize e(G - V(R)), proves the switching Lemma 3.2 within the paper, decomposes saturating non-edges into the disjoint classes ℓ1 and ℓ2 in (14) and (15), and then minimizes the resulting function Fα(r) by calculus. The critical point xp(λ) appears as the unique positive root of the polynomial Qλ, not by reverse-engineering Φp(λ); the endpoint checks xp(0), xp(1), and Φp(1) are computed from the formula and agree with known external results, but Theorems 1.1 and 1.2 are used only as context and comparison, not as inputs to the proof. Theorem 1.4 is likewise derived directly: the upper bound is a disjoint union of balanced complete bipartite graphs, and the lower bound follows from the componentwise estimates proved in Theorem 4.5 and the partition replacement in Lemma 4.6, all established in the paper. The references to prior work [5,6,7] are not author-overlapping and are not load-bearing. The minor algebraic slip noted in the proof of Lemma 3.1 concerns a displayed equality and is corrected by the surrounding argument; it does not constitute circularity. No quantity is defined in terms of the target value, and no fitted parameter is renamed as a prediction, so the circularity burden is zero.

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

The paper introduces no free parameters fitted to data: x_p(λ), y_p(λ), Φ_p(λ) are defined mathematically from the root of a polynomial that arises from an optimization, and λ is an input variable. The proofs rely only on standard results in extremal graph theory and basic analysis. No new entities such as particles, forces, or dimensions are introduced.

assumptions (4)
  • standard math Turán's theorem: an n-vertex K_{r+1}-free graph has at most t_r(n) edges, with equality only for T_r(n).
    Used in Section 3 to bound e(H) for K_p-free H and e(G[V(R)]) for the K_{p+1}-free induced subgraph, and in the f_3 lower bound via Mantel's theorem.
  • standard math Mantel's theorem: the maximum edges in a triangle-free graph is floor(n^2/4).
    Used in Section 4 to bound e_j ≤ t(q_j) and in the special case f_3(n,t(n))=s(n).
  • standard math Descartes' rule of signs and the implicit function theorem.
    Used in Lemma 2.1 to show the polynomial (2) has a unique positive root and that x_p(λ), y_p(λ), Φ_p(λ) are continuously differentiable on [0,1].
  • standard math Convexity of the pair-counting function for partitioning z n vertices into p-1 classes.
    Used in Proposition 3.3 to lower bound ℓ2 by z^2 n^2/(2(p-1)) - zn/2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Clique-saturating non-edges throughout the Tur\'an range." pith.science (2026). https://pith.science/paper/N3AWTETL

@misc{pith2026260825831,
  author       = {Pith},
  title        = {Pith review of: Clique-saturating non-edges throughout the Tur\'an range},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N3AWTETL}},
  note         = {Machine review of arXiv:2608.25831}
}
abstract

For an $F$-free graph $G$, a non-edge is $F$-saturating if adding it to $G$ creates a copy of $F$. We denote by $f_{p+1}(n,m)$ the minimum number of $K_{p+1}$-saturating non-edges in a $K_{p+1}$-free $n$-vertex graph with $m$ edges. Erd\H{o}s and Tuza conjectured that $f_4\left(n,\mathrm{ex}(n,K_3)+ 1\right)= (1 + o(1)) \frac{n^2}{16}$. Balogh and Liu (JCTB, 2014) disproved this conjecture and determined the asymptotic value of $f_4(n,\mathrm{ex}(n,K_3)+1)$. He, Ma, Ma and Ye (JCTB, 2023) later determined $f_{p+1}(n,\mathrm{ex}(n,K_p)+1)$ asymptotically for every $p\ge 3$, and asked for the value of $f_{p+1}(n,m)$ for all $\mathrm{ex}(n,K_p)+1\le m\le \mathrm{ex}(n,K_{p+1})$ and every $p\ge 3$. In this paper, we answer their question asymptotically for all $\mathrm{ex}(n,K_p)+1\le m\le \mathrm{ex}(n,K_{p+1})$ and every $p\ge 3$. We also determine the exact value of $f_3(n,m)$ for all $0\le m\le \mathrm{ex}(n,K_3)$ by a different method.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

7 extracted references · 6 canonical work pages

  1. [7]

    J. He, F. Ma, J. Ma, X. Ye, The minimum number of clique-saturating edges,J. Combin. Theory Ser. B159(2023), 42–60. 17

    work page 2023

  2. [1]

    Mantel, Problem 28,Wiskundige Opgaven10(1907), 60–61

    W. Mantel, Problem 28,Wiskundige Opgaven10(1907), 60–61

    1907

  3. [2]

    Turán, Eine Extremalaufgabe aus der Graphentheorie,Mat

    P. Turán, Eine Extremalaufgabe aus der Graphentheorie,Mat. Fiz. Lapok 48(1941), 436–452

    work page 1941

  4. [3]

    A. A. Zykov, On some properties of linear complexes,Mat. Sb. (N.S.) 24(66)(1949), 163–188 (in Russian)

    work page 1949

  5. [4]

    Erdős, A

    P. Erdős, A. Hajnal, J. W. Moon, A problem in graph theory,Amer. Math. Monthly71(1964), 1107–1110

    work page 1964

  6. [5]

    Erdős, Some of my old and new combinatorial problems, in: B

    P. Erdős, Some of my old and new combinatorial problems, in: B. Korte, L. Lovász, H.-J. Prömel, A. Schrijver (Eds.),Paths, Flows, and VLSI- Layout, Algorithms and Combinatorics, Vol. 9, Springer, Berlin, 1990, pp. 35–45. 16

    work page 1990

  7. [6]

    Balogh, H

    J. Balogh, H. Liu, On the number ofK4-saturating edges,J. Combin. Theory Ser. B109(2014), 250–257

    work page 2014

Pith tools

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