/- 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. -/ module public import FormalConjecturesUtil

Erdős Problem 766

References:

    erdosproblems.com/766

    [Er64c] Erdős, P., Extremal problems in graph theory. Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963) (1964), 29-36. PDF

@[expose] public sectionopen Filteropen scoped SimpleGraphnamespace Erdos766

$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.

noncomputable def forcingNumber (n k l : ℕ) : ℕ := sInf {m : ℕ | ∀ G : SimpleGraph (Fin n), G.edgeSet.ncard = m → ∃ H : SimpleGraph (Fin k), H.edgeSet.ncard = l ∧ H ⊑ G}

If every graph with $n$ vertices and $m$ edges contains a graph with $k$ vertices and $l$ edges, then $f(n;k,l) \leq m$.

@[category API, AMS 5] theorem forcingNumber_le {n k l m : ℕ} (h : ∀ G : SimpleGraph (Fin n), G.edgeSet.ncard = m → ∃ H : SimpleGraph (Fin k), H.edgeSet.ncard = l ∧ H ⊑ G) : forcingNumber n k l ≤ m := Nat.sInf_le h

For $k \leq n$ every graph on $n$ vertices contains the empty graph on $k$ vertices, so $f(n;k,0) = 0$.

@[category test, AMS 5] theorem forcingNumber_zero {n k : ℕ} (hkn : k ≤ n) : forcingNumber n k 0 = 0 := Nat.eq_zero_of_le_zero <| forcingNumber_le fun _ _ ↦ ⟨⊥, n:ℕk:ℕhkn:k ≤ nx✝¹:SimpleGraph (Fin n)x✝:x✝¹.edgeSet.ncard = 0⊢ ⊥.edgeSet.ncard = 0 All goals completed! 🐙, SimpleGraph.bot_isContained_iff_card_le.2 (n:ℕk:ℕhkn:k ≤ nx✝¹:SimpleGraph (Fin n)x✝:x✝¹.edgeSet.ncard = 0⊢ Fintype.card (Fin k) ≤ Fintype.card (Fin n) All goals completed! 🐙)⟩

$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$.

n:ℕk:ℕl:ℕG:SimpleGraph (Fin k)h:G.edgeSet.ncard = lG':SimpleGraph (Fin n)hG':G'.edgeSet.ncard = SimpleGraph.extremalNumber n G + 1⊢ SimpleGraph.extremalNumber n G < SimpleGraph.extremalNumber n G + 1 All goals completed! 🐙

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.

noncomputable def minExtremalNumber (n k l : ℕ) : ℕ∞ := ⨅ (G : SimpleGraph (Fin k)) (_ : G.edgeSet.ncard = l), (SimpleGraph.extremalNumber n G : ℕ∞)

The minimum is at most $\mathrm{ex}(n;G)$ for every graph $G$ with $k$ vertices and $l$ edges.

@[category API, AMS 5] theorem minExtremalNumber_le (n : ℕ) {k l : ℕ} (G : SimpleGraph (Fin k)) (h : G.edgeSet.ncard = l) : minExtremalNumber n k l ≤ SimpleGraph.extremalNumber n G := iInf₂_le G h

There is no graph with $0$ vertices and $1$ edge, so the minimum is ⊤.

@[category test, AMS 5] theorem minExtremalNumber_zero_one (n : ℕ) : minExtremalNumber n 0 1 = ⊤ := n:ℕ⊢ minExtremalNumber n 0 1 = ⊤ All goals completed! 🐙def erdos_766.parts.i.answer : ℕ → ℕ → ℕ → ℝ := sorry

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.

@[category research open, question value, AMS 5] theorem erdos_766.parts.i : ∀ k l : ℕ, k < l → l ≤ k ^ 2 / 4 → (fun n ↦ (forcingNumber n k l : ℝ)) =Θ[atTop] erdos_766.parts.i.answer k l := ⊢ ∀ (k l : ℕ), k < l → l ≤ k ^ 2 / 4 → (fun n ↦ ↑(forcingNumber n k l)) =Θ[atTop] i.answer k l All goals completed! 🐙

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.

@[category research open, question, AMS 5] theorem erdos_766.parts.ii : ∀ k : ℕ, ∀ᶠ n : ℕ in atTop, StrictMonoOn (forcingNumber n k) (Set.Ioc k (k ^ 2 / 4)) := ⊢ ∀ (k : ℕ), ∀ᶠ (n : ℕ) in atTop, StrictMonoOn (forcingNumber n k) (Set.Ioc k (k ^ 2 / 4)) All goals completed! 🐙

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.

@[category research solved, AMS 5] theorem erdos_766.variants.dirac_erdos (n k : ℕ) (hk : 3 ≤ k) (hkn : k ≤ n) : forcingNumber n k (k ^ 2 / 4 + 1) ≤ n ^ 2 / 4 + 1 := n:ℕk:ℕhk:3 ≤ khkn:k ≤ n⊢ forcingNumber n k (k ^ 2 / 4 + 1) ≤ n ^ 2 / 4 + 1 All goals completed! 🐙def erdos_766.variants.minExtremalNumber_estimate.answer : ℕ → ℕ → ℕ → ℝ := sorry

The estimate question of Erdos766.erdos_766.parts.i for the function $\min \mathrm{ex}(n;G)$ of erdosproblems.com (Erdos766.minExtremalNumber).

@[category research open, question value, AMS 5] theorem erdos_766.variants.minExtremalNumber_estimate : ∀ k l : ℕ, k < l → l ≤ k ^ 2 / 4 → (fun n ↦ ((minExtremalNumber n k l).toNat : ℝ)) =Θ[atTop] erdos_766.variants.minExtremalNumber_estimate.answer k l := ⊢ ∀ (k l : ℕ), k < l → l ≤ k ^ 2 / 4 → (fun n ↦ ↑(minExtremalNumber n k l).toNat) =Θ[atTop] minExtremalNumber_estimate.answer k l All goals completed! 🐙

The monotonicity question of Erdos766.erdos_766.parts.ii for the function $\min \mathrm{ex}(n;G)$ of erdosproblems.com (Erdos766.minExtremalNumber).

@[category research open, question, AMS 5] theorem erdos_766.variants.minExtremalNumber_strictMonoOn : ∀ k : ℕ, ∀ᶠ n : ℕ in atTop, StrictMonoOn (minExtremalNumber n k) (Set.Ioc k (k ^ 2 / 4)) := ⊢ ∀ (k : ℕ), ∀ᶠ (n : ℕ) in atTop, StrictMonoOn (minExtremalNumber n k) (Set.Ioc k (k ^ 2 / 4)) All goals completed! 🐙end Erdos766