/- 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 902

References:

    erdosproblems.com/902

    [Er63c] Erdős, P., On a problem in graph theory. Math. Gaz. 47 (1963), 220-223. PDF

    [Er82e] Erdős, Paul, Some of my favourite problems which recently have been solved. (1982), 59-79.

    [SzSz65] Szekeres, E. and Szekeres, G., On a problem of Schütte and Erdős. Math. Gaz. 49 (1965), 290-293.

@[expose] public sectionopen Filter Asymptoticsnamespace Erdos902

HasPropertyS G n is Schütte's property $S_n$ [Er63c]: every set E of n vertices is dominated by a vertex outside it, that is, some vertex x ∉ E has an edge to every vertex of E.

def HasPropertyS {V : Type*} (G : Digraph V) (n : ℕ) : Prop := ∀ E : Finset V, E.card = n → ∃ x ∉ E, ∀ e ∈ E, G.Adj x e

$f(n)$: the least number of vertices of a tournament with property $S_n$.

A tournament with fewer than $n$ vertices has no set of $n$ vertices, so it has property $S_n$ vacuously; the condition n ≤ m excludes this case.

noncomputable def f (n : ℕ) : ℕ := sInf {m : ℕ | n ≤ m ∧ ∃ G : Digraph (Fin m), G.IsTournament ∧ HasPropertyS G n}

The cyclic tournament on three vertices, a → a + 1, has property $S_1$, so $f(1) \leq 3$.

a:Fin 3hE:{a}.card = 1key:∀ (a : Fin 3), a + 2 ≠ a ∧ a = a + 2 + 1e:Fin 3he:e ∈ {a}⊢ { Adj := fun a b ↦ b = a + 1 }.Adj (a + 2) a All goals completed! 🐙

Erdős's tournament on seven vertices [Er63c], with a → a + 1, a + 2, a + 4 modulo $7$, has property $S_2$, so $f(2) \leq 7$.

a:Fin 7b:Fin 7hab:a ≠ bhE:{a, b}.card = 2key:∀ (a b : Fin 7), a ≠ b → ∃ x, x ≠ a ∧ x ≠ b ∧ a - x ∈ {1, 2, 4} ∧ b - x ∈ {1, 2, 4}x:Fin 7hxa:x ≠ ahxb:x ≠ bha:a - x ∈ {1, 2, 4}hb:b - x ∈ {1, 2, 4}e:Fin 7he✝:e ∈ {a, b}he:e ∈ {b}⊢ { Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj x b All goals completed! 🐙def erdos_902.answer : ℕ → ℝ := sorry

Let $f(n)$ be minimal such that there is a tournament (a complete directed graph) on $f(n)$ vertices such that every set of $n$ vertices is dominated by at least one other vertex. Estimate $f(n)$.

@[category research open, question value, AMS 5] theorem erdos_902 : (fun n ↦ (f n : ℝ)) =Θ[atTop] erdos_902.answer := ⊢ (fun n ↦ ↑(f n)) =Θ[atTop] erdos_902.answer All goals completed! 🐙

It is easy to check that $f(1)=3$ and $f(2)=7$.

This is the statement for $f(1)$.

m:ℕhm:1 ≤ 2G:Digraph (Fin 2)hG:G.IsTournamenthS:HasPropertyS G 1hm3:2 < 3h01:G.Adj 0 1 ↔ ¬G.Adj 1 0h:¬G.Adj 0 1x:Fin 2hx:x ∉ {1}hx1:∀ e ∈ {1}, G.Adj x ehx0:x = 0⊢ False m:ℕhm:1 ≤ 2G:Digraph (Fin 2)hG:G.IsTournamenthS:HasPropertyS G 1hm3:2 < 3h01:G.Adj 0 1 ↔ ¬G.Adj 1 0h:¬G.Adj 0 1hx:0 ∉ {1}hx1:∀ e ∈ {1}, G.Adj 0 e⊢ False exact h (hx1 1 (m:ℕhm:1 ≤ 2G:Digraph (Fin 2)hG:G.IsTournamenthS:HasPropertyS G 1hm3:2 < 3h01:G.Adj 0 1 ↔ ¬G.Adj 1 0h:¬G.Adj 0 1hx:0 ∉ {1}hx1:∀ e ∈ {1}, G.Adj 0 e⊢ 1 ∈ {1} All goals completed! 🐙))

It is easy to check that $f(1)=3$ and $f(2)=7$.

This is the statement for $f(2)$.

@[category research solved, AMS 5] theorem erdos_902.variants.f_two : f 2 = 7 := ⊢ f 2 = 7 All goals completed! 🐙

Erdős [Er63c] proved $$2^{n+1}-1 \leq f(n) \ll n^22^n.$$

This is the lower bound.

@[category research solved, AMS 5] theorem erdos_902.variants.erdos_lower (n : ℕ) : 2 ^ (n + 1) - 1 ≤ f n := n:ℕ⊢ 2 ^ (n + 1) - 1 ≤ f n All goals completed! 🐙

Erdős [Er63c] proved $$2^{n+1}-1 \leq f(n) \ll n^22^n.$$

This is the upper bound, in the form proved in [Er63c, (2)]: $\limsup_n f(n)2^{-n}n^{-2} \leq \log 2$.

@[category research solved, AMS 5] theorem erdos_902.variants.erdos_upper : ∀ ε > (0 : ℝ), ∀ᶠ n : ℕ in atTop, (f n : ℝ) ≤ (Real.log 2 + ε) * n ^ 2 * 2 ^ n := ⊢ ∀ ε > 0, ∀ᶠ (n : ℕ) in atTop, ↑(f n) ≤ (Real.log 2 + ε) * ↑n ^ 2 * 2 ^ n All goals completed! 🐙

Szekeres and Szekeres [SzSz65] proved that $f(3)=19$ and $$n2^n \ll f(n).$$

This is the statement for $f(3)$.

@[category research solved, AMS 5] theorem erdos_902.variants.szekeres_f_three : f 3 = 19 := ⊢ f 3 = 19 All goals completed! 🐙

Szekeres and Szekeres [SzSz65] proved that $f(3)=19$ and $$n2^n \ll f(n).$$

This is the lower bound.

@[category research solved, AMS 5] theorem erdos_902.variants.szekeres_lower : ∃ c > (0 : ℝ), ∀ᶠ n : ℕ in atTop, c * n * 2 ^ n ≤ (f n : ℝ) := ⊢ ∃ c > 0, ∀ᶠ (n : ℕ) in atTop, c * ↑n * 2 ^ n ≤ ↑(f n) All goals completed! 🐙end Erdos902