Across the full Turán edge range, a new theoretical result identifies the leading size of the smallest possible number of missing links that would create a forbidden clique when added. For every fixed p ≥ 3, the paper proves that f_{p+1}(n,m) = Φ_p(λ)n² + O_p(n) whenever t_{p−1}(n) < m ≤ t_p(n). In plain language, the minimum follows a quadratic profile throughout the interval between the two stated edge-count thresholds, with an asymptotic remainder rather than an exact finite-size formula.
The paper calls such a missing link an F-saturating non-edge: adding it creates a copy of F. Here the main theorem concerns finite simple graphs that are K_{p+1}-free, meaning they contain no clique of p+1 vertices. The question is therefore about the smallest possible number of absent edges that are one addition away from creating the forbidden clique.
An exact answer for triangles
The separate p=2 result gives an exact answer for triangles. For every n ≥ 1 and 0 ≤ m ≤ t(n), f_3(n,m) equals a minimum over partitions q_1+⋯+q_k=n. The permitted partitions are those for which the total of the paper's t(q_i) terms is at least m, and the expression minimized is the corresponding sum of s(q_i). In practical terms, the triangle problem becomes a finite search over ways of dividing n into part sizes.
That exact minimum is zero precisely when m ≤ ⌊n/2⌋. So throughout the matching range, no triangle-creating non-edges are needed in a minimizing construction; once m is larger, the partition optimization supplies the exact minimum.
The finite optimization can be computed by a dynamic program. The proof's upper bound uses disjoint unions of balanced complete bipartite graphs—graphs split into two nearly equal sides with all cross-links present—and deletes edges when necessary. Its lower bound comes from componentwise estimates for connected triangle-free graphs.
How the asymptotic result is pinned down
For p ≥ 3, the upper-bound construction uses blow-ups: each vertex is replaced by a group while the original adjacency pattern is retained. To prove the lower bound, the authors take a maximum collection of vertex-disjoint K_p subgraphs, then use switching and classify the saturating non-edges before reducing the problem to a one-variable optimization.
An intermediate lower-bound proposition makes that argument quantitative. Every n-vertex K_{p+1}-free graph with m > t_{p−1}(n) edges satisfies f_{p+1}(G) ≥ F_α(|R|/n)n² − O_p(n), giving a lower bound on its number of saturating non-edges. The proof then shows F_α(r) ≥ Φ_p(λ) for every 0 < r ≤ 1/p, establishing the profile needed for the full-range theorem.
At the upper Turán endpoint, the paper gives f_{p+1}(n,t_p(n)) = n²/(2p) + O_p(n). At the lower threshold itself, m = t_{p−1}(n), the minimum is zero. But Φ_p(0) is the right-hand limit just above that threshold, not the threshold value itself.
What remains unresolved
The general result is deliberately asymptotic. Its O_p(n) remainder does not determine the linear term uniformly across the p ≥ 3 interval. Nor does asymptotic optimality identify all extremal graphs—the graphs that attain the minimum. The authors list stability and the uniform linear term as open questions.
For triangles, the exact statement is a finite partition optimization, and it is algorithmically accessible through the dynamic program. Together, the results give an exact finite solution for p=2 and a leading-order solution for every fixed p ≥ 3 over the graph classes and edge ranges stated in the paper.
The document is an arXiv version 1 preprint dated 26 August 2026.
Paper data and sources
Original title: Clique-saturating non-edges throughout the Turán range
Authors: Xiaolin Wang, Jiabao Yang, Ruilin Zheng
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text