/-
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 FormalConjecturesUtilErdős Problem 902
References:
[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
exact (key a).2 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$.
@[category test, AMS 5]
theorem f_two_le : f 2 ≤ 7 := by ⊢ f 2 ≤ 7
refine Nat.sInf_le ⟨by ⊢ 2 ≤ 7 norm_num All goals completed! 🐙, ⟨fun a b => b - a ∈ ({1, 2, 4} : Finset (Fin 7))⟩,
⟨by ⊢ ∀ (v : Fin 7), ¬{ Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj v v decide All goals completed! 🐙, by ⊢ ∀ (u v : Fin 7),
u ≠ v → ({ Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj u v ↔ ¬{ Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj v u) decide All goals completed! 🐙⟩, ?_⟩
intro E hE E:Finset (Fin 7)hE:E.card = 2⊢ ∃ x ∉ E, ∀ e ∈ E, { Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj x e
obtain ⟨a, b, hab, rfl⟩ := Finset.card_eq_two.1 hE a:Fin 7b:Fin 7hab:a ≠ bhE:{a, b}.card = 2⊢ ∃ x ∉ {a, b}, ∀ e ∈ {a, b}, { Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj x e
have key : ∀ a b : Fin 7, a ≠ b → ∃ x, x ≠ a ∧ x ≠ b ∧
a - x ∈ ({1, 2, 4} : Finset (Fin 7)) ∧ b - x ∈ ({1, 2, 4} : Finset (Fin 7)) := by ⊢ f 2 ≤ 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 ∉ {a, b}, ∀ e ∈ {a, b}, { Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj x e
decide 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 ∉ {a, b}, ∀ e ∈ {a, b}, { Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj x e 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 ∉ {a, b}, ∀ e ∈ {a, b}, { Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj x e
obtain ⟨x, hxa, hxb, ha, hb⟩ := key a b hab 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}⊢ ∃ x ∉ {a, b}, ∀ e ∈ {a, b}, { Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj x e
refine ⟨x, by 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}⊢ x ∉ {a, b} simp [hxa, hxb] All goals completed! 🐙, fun e he => ?_⟩
rcases Finset.mem_insert.1 he with rfl | he inl b:Fin 7key:∀ (a b : Fin 7), a ≠ b → ∃ x, x ≠ a ∧ x ≠ b ∧ a - x ∈ {1, 2, 4} ∧ b - x ∈ {1, 2, 4}x:Fin 7hxb:x ≠ bhb:b - x ∈ {1, 2, 4}e:Fin 7hab:e ≠ bhE:{e, b}.card = 2hxa:x ≠ eha:e - x ∈ {1, 2, 4}he:e ∈ {e, b}⊢ { Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj x einr 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 e
· inl b:Fin 7key:∀ (a b : Fin 7), a ≠ b → ∃ x, x ≠ a ∧ x ≠ b ∧ a - x ∈ {1, 2, 4} ∧ b - x ∈ {1, 2, 4}x:Fin 7hxb:x ≠ bhb:b - x ∈ {1, 2, 4}e:Fin 7hab:e ≠ bhE:{e, b}.card = 2hxa:x ≠ eha:e - x ∈ {1, 2, 4}he:e ∈ {e, b}⊢ { Adj := fun a b ↦ b - a ∈ {1, 2, 4} }.Adj x e exact ha All goals completed! 🐙
· inr 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 e rw [Finset.mem_singleton.1 he inr 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 inr 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]inr 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
exact hb All goals completed! 🐙def erdos_902.answer : ℕ → ℝ := sorryLet $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 := by ⊢ (fun n ↦ ↑(f n)) =Θ[atTop] erdos_902.answer
sorry All goals completed! 🐙It is easy to check that $f(1)=3$ and $f(2)=7$.
This is the statement for $f(1)$.
@[category research solved, AMS 5]
theorem erdos_902.variants.f_one : f 1 = 3 := by ⊢ f 1 = 3
refine le_antisymm f_one_le (le_csInf ⟨3, ?_⟩ ?_) refine_1 ⊢ 3 ∈ {m | 1 ≤ m ∧ ∃ G, G.IsTournament ∧ HasPropertyS G 1}refine_2 ⊢ ∀ b ∈ {m | 1 ≤ m ∧ ∃ G, G.IsTournament ∧ HasPropertyS G 1}, 3 ≤ b
· refine_1 ⊢ 3 ∈ {m | 1 ≤ m ∧ ∃ G, G.IsTournament ∧ HasPropertyS G 1} refine ⟨by ⊢ 1 ≤ 3 norm_num All goals completed! 🐙, ⟨fun a b => b = a + 1⟩, ⟨by ⊢ ∀ (v : Fin 3), ¬{ Adj := fun a b ↦ b = a + 1 }.Adj v v decide All goals completed! 🐙, by ⊢ ∀ (u v : Fin 3), u ≠ v → ({ Adj := fun a b ↦ b = a + 1 }.Adj u v ↔ ¬{ Adj := fun a b ↦ b = a + 1 }.Adj v u) decide All goals completed! 🐙⟩, ?_⟩
intro E hE refine_1 E:Finset (Fin 3)hE:E.card = 1⊢ ∃ x ∉ E, ∀ e ∈ E, { Adj := fun a b ↦ b = a + 1 }.Adj x e
obtain ⟨a, rfl⟩ := Finset.card_eq_one.1 hE refine_1 a:Fin 3hE:{a}.card = 1⊢ ∃ x ∉ {a}, ∀ e ∈ {a}, { Adj := fun a b ↦ b = a + 1 }.Adj x e
have key : ∀ a : Fin 3, a + 2 ≠ a ∧ a = a + 2 + 1 := by ⊢ f 1 = 3 refine_1 a:Fin 3hE:{a}.card = 1key:∀ (a : Fin 3), a + 2 ≠ a ∧ a = a + 2 + 1⊢ ∃ x ∉ {a}, ∀ e ∈ {a}, { Adj := fun a b ↦ b = a + 1 }.Adj x e decide refine_1 a:Fin 3hE:{a}.card = 1key:∀ (a : Fin 3), a + 2 ≠ a ∧ a = a + 2 + 1⊢ ∃ x ∉ {a}, ∀ e ∈ {a}, { Adj := fun a b ↦ b = a + 1 }.Adj x erefine_1 a:Fin 3hE:{a}.card = 1key:∀ (a : Fin 3), a + 2 ≠ a ∧ a = a + 2 + 1⊢ ∃ x ∉ {a}, ∀ e ∈ {a}, { Adj := fun a b ↦ b = a + 1 }.Adj x e
refine ⟨a + 2, by a:Fin 3hE:{a}.card = 1key:∀ (a : Fin 3), a + 2 ≠ a ∧ a = a + 2 + 1⊢ a + 2 ∉ {a} simp [(key a).1] All goals completed! 🐙, fun e he => ?_⟩
rw [Finset.mem_singleton.1 he refine_1 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 refine_1 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]refine_1 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
exact (key a).2 All goals completed! 🐙
· refine_2 ⊢ ∀ b ∈ {m | 1 ≤ m ∧ ∃ G, G.IsTournament ∧ HasPropertyS G 1}, 3 ≤ b rintro m ⟨hm, G, hG, hS⟩ refine_2 m:ℕhm:1 ≤ mG:Digraph (Fin m)hG:G.IsTournamenthS:HasPropertyS G 1⊢ 3 ≤ m
by_contra! hm3 refine_2 m:ℕhm:1 ≤ mG:Digraph (Fin m)hG:G.IsTournamenthS:HasPropertyS G 1hm3:m < 3⊢ False
interval_cases m refine_2.«1» m:ℕhm:1 ≤ 1G:Digraph (Fin 1)hG:G.IsTournamenthS:HasPropertyS G 1hm3:1 < 3⊢ Falserefine_2.«2» m:ℕhm:1 ≤ 2G:Digraph (Fin 2)hG:G.IsTournamenthS:HasPropertyS G 1hm3:2 < 3⊢ False
· refine_2.«1» m:ℕhm:1 ≤ 1G:Digraph (Fin 1)hG:G.IsTournamenthS:HasPropertyS G 1hm3:1 < 3⊢ False obtain ⟨x, hx, -⟩ := hS {0} rfl refine_2.«1» m:ℕhm:1 ≤ 1G:Digraph (Fin 1)hG:G.IsTournamenthS:HasPropertyS G 1hm3:1 < 3x:Fin 1hx:x ∉ {0}⊢ False
exact hx (by m:ℕhm:1 ≤ 1G:Digraph (Fin 1)hG:G.IsTournamenthS:HasPropertyS G 1hm3:1 < 3x:Fin 1hx:x ∉ {0}⊢ x ∈ {0} simp [Subsingleton.elim x 0] All goals completed! 🐙)
· refine_2.«2» m:ℕhm:1 ≤ 2G:Digraph (Fin 2)hG:G.IsTournamenthS:HasPropertyS G 1hm3:2 < 3⊢ False have h01 := hG.2 0 1 (by m:ℕhm:1 ≤ 2G:Digraph (Fin 2)hG:G.IsTournamenthS:HasPropertyS G 1hm3:2 < 3⊢ 0 ≠ 1 refine_2.«2» m:ℕhm:1 ≤ 2G:Digraph (Fin 2)hG:G.IsTournamenthS:HasPropertyS G 1hm3:2 < 3h01:G.Adj 0 1 ↔ ¬G.Adj 1 0⊢ False decide All goals completed! 🐙refine_2.«2» m:ℕhm:1 ≤ 2G:Digraph (Fin 2)hG:G.IsTournamenthS:HasPropertyS G 1hm3:2 < 3h01:G.Adj 0 1 ↔ ¬G.Adj 1 0⊢ False)refine_2.«2» m:ℕhm:1 ≤ 2G:Digraph (Fin 2)hG:G.IsTournamenthS:HasPropertyS G 1hm3:2 < 3h01:G.Adj 0 1 ↔ ¬G.Adj 1 0⊢ False
by_cases h : G.Adj 0 1 pos 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 1⊢ Falseneg 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 1⊢ False
· pos 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 1⊢ False obtain ⟨x, hx, hx0⟩ := hS {0} rfl pos 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 ∉ {0}hx0:∀ e ∈ {0}, G.Adj x e⊢ False
have hx1 : x = 1 := by ⊢ f 1 = 3 pos 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 ∉ {0}hx0:∀ e ∈ {0}, G.Adj x ehx1:x = 1⊢ False fin_cases x «0» 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:(fun i ↦ i) ⟨0, ⋯⟩ ∉ {0}hx0:∀ e ∈ {0}, G.Adj ((fun i ↦ i) ⟨0, ⋯⟩) e⊢ (fun i ↦ i) ⟨0, ⋯⟩ = 1«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:(fun i ↦ i) ⟨1, ⋯⟩ ∉ {0}hx0:∀ e ∈ {0}, G.Adj ((fun i ↦ i) ⟨1, ⋯⟩) e⊢ (fun i ↦ i) ⟨1, ⋯⟩ = 1pos 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 ∉ {0}hx0:∀ e ∈ {0}, G.Adj x ehx1:x = 1⊢ False <;> «0» 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:(fun i ↦ i) ⟨0, ⋯⟩ ∉ {0}hx0:∀ e ∈ {0}, G.Adj ((fun i ↦ i) ⟨0, ⋯⟩) e⊢ (fun i ↦ i) ⟨0, ⋯⟩ = 1«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:(fun i ↦ i) ⟨1, ⋯⟩ ∉ {0}hx0:∀ e ∈ {0}, G.Adj ((fun i ↦ i) ⟨1, ⋯⟩) e⊢ (fun i ↦ i) ⟨1, ⋯⟩ = 1pos 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 ∉ {0}hx0:∀ e ∈ {0}, G.Adj x ehx1:x = 1⊢ False simp_allpos 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 ∉ {0}hx0:∀ e ∈ {0}, G.Adj x ehx1:x = 1⊢ Falsepos 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 ∉ {0}hx0:∀ e ∈ {0}, G.Adj x ehx1:x = 1⊢ False
subst hx1 pos 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:1 ∉ {0}hx0:∀ e ∈ {0}, G.Adj 1 e⊢ False
exact h01.1 h (hx0 0 (by 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:1 ∉ {0}hx0:∀ e ∈ {0}, G.Adj 1 e⊢ 0 ∈ {0} simp All goals completed! 🐙))
· neg 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 1⊢ False obtain ⟨x, hx, hx1⟩ := hS {1} rfl neg 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 e⊢ False
have hx0 : x = 0 := by ⊢ f 1 = 3 neg 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 fin_cases x «0» 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:(fun i ↦ i) ⟨0, ⋯⟩ ∉ {1}hx1:∀ e ∈ {1}, G.Adj ((fun i ↦ i) ⟨0, ⋯⟩) e⊢ (fun i ↦ i) ⟨0, ⋯⟩ = 0«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:(fun i ↦ i) ⟨1, ⋯⟩ ∉ {1}hx1:∀ e ∈ {1}, G.Adj ((fun i ↦ i) ⟨1, ⋯⟩) e⊢ (fun i ↦ i) ⟨1, ⋯⟩ = 0neg 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 <;> «0» 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:(fun i ↦ i) ⟨0, ⋯⟩ ∉ {1}hx1:∀ e ∈ {1}, G.Adj ((fun i ↦ i) ⟨0, ⋯⟩) e⊢ (fun i ↦ i) ⟨0, ⋯⟩ = 0«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:(fun i ↦ i) ⟨1, ⋯⟩ ∉ {1}hx1:∀ e ∈ {1}, G.Adj ((fun i ↦ i) ⟨1, ⋯⟩) e⊢ (fun i ↦ i) ⟨1, ⋯⟩ = 0neg 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 simp_allneg 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⊢ Falseneg 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
subst hx0 neg 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 (by 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} simp 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 := by ⊢ f 2 = 7
sorry 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 := by n:ℕ⊢ 2 ^ (n + 1) - 1 ≤ f n
sorry 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 := by ⊢ ∀ ε > 0, ∀ᶠ (n : ℕ) in atTop, ↑(f n) ≤ (Real.log 2 + ε) * ↑n ^ 2 * 2 ^ n
sorry 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 := by ⊢ f 3 = 19
sorry 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 : ℝ) := by ⊢ ∃ c > 0, ∀ᶠ (n : ℕ) in atTop, c * ↑n * 2 ^ n ≤ ↑(f n)
sorry All goals completed! 🐙end Erdos902