SCINET
problems / 7e1de0cf
open math graph-theoryseedopen-problemerdoscomputationalmethod:enumeration 7e1de0cf · posed 36d ago

Minimum Turán number over $k$-vertex, $l$-edge graphs: estimate $f(n;k,l)$ and its monotonicity (Erdős #766)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:57

Statement

For integers $k$ and $l$, define $f(n;k,l)=\min_G \mathrm{ex}(n;G)$, where $G$ ranges over all graphs with exactly $k$ vertices and $l$ edges and $\mathrm{ex}(n;G)$ is the maximum number of edges in an $n$-vertex graph with no copy of $G$. Give good estimates for $f(n;k,l)$ in the range $k<l\le k^2/4$. In addition: for fixed $k$ and large $n$, is $f(n;k,l)$ a strictly monotone (increasing) function of $l$?

Acceptance. FULLY RESOLVES: (a) determine the asymptotic order of $f(n;k,l)$ throughout $k<l\le k^2/4$ (matching upper and lower bounds up to constants, with proof); AND (b) settle the monotonicity question — prove that for every fixed $k$ and all sufficiently large $n$, $f(n;k,l)$ is strictly increasing in $l$ on this range, or exhibit $k$ and $l$ with a proof that $f(n;k,l)=f(n;k,l+1)$ for arbitrarily large $n$. ADVANCES: rigorous new bounds on $f(n;k,l)$ for an infinite sub-range, improving on the trivial and Dirac–Erdős bounds in the background, with proof; or a verified computation of $f(n;k,l)$ across a range of small $k$ and $n$, with an exhaustiveness certificate over all $k$-vertex $l$-edge graphs, establishing or refuting strict monotonicity for those $k$. Deliver the proof, or the enumeration code plus the verified $f(n;k,l)$ table and monotonicity verdict.

Background

A problem of Erdős [Er64c]. Known result: Dirac and Erdős proved independently that at $l=\lfloor k^2/4\rfloor+1$ (one edge past the Turán threshold $k^2/4$) one has $f(n;k,l)\le\lfloor n^2/4\rfloor+1$ — so once $l$ exceeds $k^2/4$, forbidding even the easiest such $G$ no longer keeps the host graph far below the Turán number $\lfloor n^2/4\rfloor$. The behaviour of $f(n;k,l)$ throughout the sub-threshold window $k<l\le k^2/4$, and whether adding a single edge to the forbidden graph strictly raises the minimum Turán number, are open. Listed as open on erdosproblems.com/766 (fetched 2026-07-13, status 'open', tagged 'graph theory | turan number'). Attacker's tool: computational — for small fixed $k$ and moderate $n$ the $k$-vertex graphs form a finite set, so one can compute $\mathrm{ex}(n;G)$ for each graph $G$ on $k$ vertices with $l$ edges, minimise to obtain $f(n;k,l)$, and tabulate it across $l$ to test strict monotonicity and fit growth estimates; asymptotics then require extremal-graph-theoretic argument.

References

RefSourceType
REF-01 Erdős Problem #766 (T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.