/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
$f(n;k,l)$ in the sense of [Er64c], where it is called $f_1(n;k,l)$: the least $m$ such that
every graph with $n$ vertices and $m$ edges contains at least one graph with $k$ vertices and
$l$ edges as a (not necessarily induced) subgraph. There is no graph with $n$ vertices and more
than $\binom{n}{2}$ edges, so the set is nonempty.
$f(n;k,l) \leq \mathrm{ex}(n;G) + 1$ for every graph $G$ with $k$ vertices and $l$ edges,
since a graph with more than $\mathrm{ex}(n;G)$ edges contains $G$. Here $\mathrm{ex}(n;G)$ is
SimpleGraph.extremalNumber n G, the maximum number of edges of a graph on $n$ vertices with no
copy of $G$.
The function of erdosproblems.com: the minimum of $\mathrm{ex}(n;G)$ over all graphs $G$ with
$k$ vertices and $l$ edges. In [Er64c] the least $m$ such that every graph with $n$ vertices and
$m$ edges contains one fixed graph with $k$ vertices and $l$ edges is called $f_2(n;k,l)$, so
this is $f_2(n;k,l) - 1$. The value is in ℕ∞ and is ⊤ when no such graph $G$ exists.
Let $f(n;k,l)=\min \mathrm{ex}(n;G)$, where $G$ ranges over all graphs with $k$ vertices and $l$
edges.
Give good estimates for $f(n;k,l)$ in the range $k<l\leq k^2/4$.
In [Er64c, p. 33] this question is asked for $f_1(n;k,l)$ (Erdos766.forcingNumber), which
forces at least one graph with $k$ vertices and $l$ edges rather than one fixed graph; we follow
the source. The question for the function of erdosproblems.com is
Erdos766.erdos_766.variants.minExtremalNumber_estimate.
For fixed $k$ and large $n$ is $f(n;k,l)$ a strictly monotone function of $l$?
As in Erdos766.erdos_766.parts.i, $f$ is $f_1$ of [Er64c], and we use the range
$k<l\leq k^2/4$ in which the question is asked there; here k ^ 2 / 4 is $\lfloor k^2/4\rfloor$.
The question for the function of erdosproblems.com is
Erdos766.erdos_766.variants.minExtremalNumber_strictMonoOn.
Dirac and Erdős proved independently that when $l=\lfloor k^2/4\rfloor+1$
$$f(n;k,l)\leq \lfloor n^2/4\rfloor+1.$$
[Er64c, p. 34] states this for every $k \leq n$. We assume $k \geq 3$, since for $k \leq 2$ there
is no graph with $k$ vertices and $\lfloor k^2/4\rfloor+1$ edges.