For an integer p≥ 3, let operatornameex(n,K_r) denote the maximum number of edges in an n-vertex K_r-free graph. For integers n and m, define f_p+1(n,m) to be the minimum, over all n-vertex K_p+1-free graphs G with m edges, of the number of non-edges xy notin E(G) such that adding xy to G creates a copy of K_p+1. Determine the asymptotic value of f_p+1(n,m), for every fixed p≥ 3, throughout the range operatornameex(n,K_p)+1≤ m≤ operatornameex(n,K_p+1).

Clique-saturating non-edges problem of He, Ma, Ma and Ye

The problem asks for the minimum number of non-edges that must be added to an $n$ -vertex graph with $m$ edges to create a new clique, throughout the range between consecutive Turán thresholds. He, Ma, Ma, and Ye established the first super-Turán value in 2022, leaving the broader range open.

Known results

He, Ma, Ma, and Ye (2022) proved the first super-Turán asymptotic:

f_{p+1}\bigl(n,\operatorname{ex}(n,K_p)+1\bigr)=\left(\frac{2(p-2)^2}{p(4p^2-11p+8)}+o(1)\right)n^2.

Their methods also cover $1\le t\le \frac{(p-2)^3}{p(p-1)(4p^2-11p+8)}n$ , with value equal to the same quadratic main term plus $\Theta(n)$ ; the rest of the Turán interval was explicitly left open.

August 26, 2026 claimed resolution

A newly reported arXiv preprint claims an asymptotic determination of $f_{p+1}(n,m)$ throughout the stated Turán range and an exact result in the triangle case, which would fill the identified gap. The claim is unrefereed and remains unverified.

Current status (as of August 2026): The first super-Turán cases and a short linear-width range are established, while full-range asymptotics and the exact triangle case are only claimed by the unverified August 2026 preprint.

Clique-saturating non-edges problem of He, Ma, Ma and Ye

Primary source

Additional references

Progress summary

Solutions 0