/-
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 813
References:
[Er91] Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406.
[BuSu23] Bucić, M. and Sudakov, B., Large independent sets from local considerations. Combinatorica 43 (2023), 505-546. arXiv:2007.03667
@[expose] public sectionopen Filter Asymptoticsnamespace Erdos813
Every set of $7$ vertices of G contains a triangle, that is, three pairwise adjacent
vertices. For $n < 7$ there is no such set, so the condition is vacuous.
def EverySevenHasTriangle {n : ℕ} (G : SimpleGraph (Fin n)) : Prop :=
∀ S : Finset (Fin n), S.card = 7 → ∃ t ⊆ S, G.IsNClique 3 t
h n is $h(n)$: the smallest clique number of a graph on $n$ vertices in which every set of
$7$ vertices contains a triangle. The complete graph satisfies the condition, so the set is
never empty and sInf is a true minimum.
noncomputable def h (n : ℕ) : ℕ :=
sInf {k : ℕ | ∃ G : SimpleGraph (Fin n), EverySevenHasTriangle G ∧ G.cliqueNum = k}The complete graph on $n$ vertices satisfies the condition.
n:ℕS:Finset (Fin n)hS:S.card = 7t:Finset (Fin n)htS:t ⊆ Sht:t.card = 3⊢ ∃ t ⊆ S, ⊤.IsNClique 3 t
exact ⟨t, htS, ⟨(SimpleGraph.isClique_univ.2 rfl).subset (Set.subset_univ _), ht⟩⟩ All goals completed! 🐙For $n = 7$ the graph must contain a triangle, and a triangle plus $4$ isolated vertices has clique number $3$, so $h(7) = 3$.
@[category test, AMS 5]
theorem h_seven : h 7 = 3 := by ⊢ h 7 = 3
-- The triangle on `{0, 1, 2}` together with four isolated vertices.
set G : SimpleGraph (Fin 7) :=
{ Adj := fun v w => v ≠ w ∧ v.val < 3 ∧ w.val < 3
symm := by ⊢ Std.Symm fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3 constructor ⊢ ∀ (a b : Fin 7), a ≠ b ∧ ↑a < 3 ∧ ↑b < 3 → b ≠ a ∧ ↑b < 3 ∧ ↑a < 3; intro v w h v:Fin 7w:Fin 7h:v ≠ w ∧ ↑v < 3 ∧ ↑w < 3⊢ w ≠ v ∧ ↑w < 3 ∧ ↑v < 3; exact ⟨h.1.symm, h.2.2, h.2.1⟩ All goals completed! 🐙
loopless := by ⊢ Std.Irrefl fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3 constructor ⊢ ∀ (a : Fin 7), ¬(a ≠ a ∧ ↑a < 3 ∧ ↑a < 3); intro v h v:Fin 7h:v ≠ v ∧ ↑v < 3 ∧ ↑v < 3⊢ False; exact h.1 rfl All goals completed! 🐙 } with hG
have hmem3 : ∀ a : Fin 7, a ∈ ({0, 1, 2} : Finset (Fin 7)) ↔ a.val < 3 := by decide G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3⊢ h 7 = 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3⊢ h 7 = 3
have htri : G.IsNClique 3 ({0, 1, 2} : Finset (Fin 7)) := by
constructor isClique G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3⊢ G.IsClique ↑{0, 1, 2}card_eq G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3⊢ {0, 1, 2}.card = 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}⊢ h 7 = 3
· isClique G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3⊢ G.IsClique ↑{0, 1, 2} G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}⊢ h 7 = 3 intro a ha b hb hab isClique G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3a:Fin 7ha:a ∈ ↑{0, 1, 2}b:Fin 7hb:b ∈ ↑{0, 1, 2}hab:a ≠ b⊢ G.Adj a b G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}⊢ h 7 = 3
exact ⟨hab, (hmem3 a).1 ha, (hmem3 b).1 hb⟩ All goals completed! 🐙 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}⊢ h 7 = 3
· card_eq G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3⊢ {0, 1, 2}.card = 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}⊢ h 7 = 3 decide G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}⊢ h 7 = 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}⊢ h 7 = 3
have hclique : G.cliqueNum = 3 := by
refine le_antisymm ?_ (htri.card_eq ▸ htri.isClique.card_le_cliqueNum) G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}⊢ G.cliqueNum ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3
obtain ⟨s, hs⟩ := G.exists_isNClique_cliqueNum G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum s⊢ G.cliqueNum ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3
rw [← hs.card_eq G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum s⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum s⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3] G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum s⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3
by_cases hcard : s.card ≤ 1 pos G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:s.card ≤ 1⊢ s.card ≤ 3neg G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3
· pos G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:s.card ≤ 1⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3 omega All goals completed! 🐙 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3
· neg G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3 have hsub : s ⊆ ({0, 1, 2} : Finset (Fin 7)) := by ⊢ h 7 = 3 neg G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1hsub:s ⊆ {0, 1, 2}⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3
intro v hv G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1v:Fin 7hv:v ∈ s⊢ v ∈ {0, 1, 2}neg G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1hsub:s ⊆ {0, 1, 2}⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3
obtain ⟨w, hw, hne⟩ := Finset.exists_mem_ne (by G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1v:Fin 7hv:v ∈ s⊢ 1 < s.card G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1v:Fin 7hv:v ∈ sw:Fin 7hw:w ∈ shne:w ≠ v⊢ v ∈ {0, 1, 2}neg G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1hsub:s ⊆ {0, 1, 2}⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3 omega All goals completed! 🐙 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1v:Fin 7hv:v ∈ sw:Fin 7hw:w ∈ shne:w ≠ v⊢ v ∈ {0, 1, 2}neg G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1hsub:s ⊆ {0, 1, 2}⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3 : 1 < s.card) v G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1v:Fin 7hv:v ∈ sw:Fin 7hw:w ∈ shne:w ≠ v⊢ v ∈ {0, 1, 2}neg G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1hsub:s ⊆ {0, 1, 2}⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3
exact (hmem3 v).2 (hs.isClique hv hw hne.symm).2.1neg G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1hsub:s ⊆ {0, 1, 2}⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3neg G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}s:Finset (Fin 7)hs:G.IsNClique G.cliqueNum shcard:¬s.card ≤ 1hsub:s ⊆ {0, 1, 2}⊢ s.card ≤ 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3
simpa using Finset.card_le_card hsub G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3⊢ h 7 = 3
have hESH : EverySevenHasTriangle G := by
intro S hS G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3S:Finset (Fin 7)hS:S.card = 7⊢ ∃ t ⊆ S, G.IsNClique 3 t G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle G⊢ h 7 = 3
have hU : S = Finset.univ := S.eq_univ_of_card (by G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3S:Finset (Fin 7)hS:S.card = 7⊢ S.card = Fintype.card (Fin 7) G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3S:Finset (Fin 7)hS:S.card = 7hU:S = Finset.univ⊢ ∃ t ⊆ S, G.IsNClique 3 t G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle G⊢ h 7 = 3 simp [hS] All goals completed! 🐙 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3S:Finset (Fin 7)hS:S.card = 7hU:S = Finset.univ⊢ ∃ t ⊆ S, G.IsNClique 3 t G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle G⊢ h 7 = 3) G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3S:Finset (Fin 7)hS:S.card = 7hU:S = Finset.univ⊢ ∃ t ⊆ S, G.IsNClique 3 t G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle G⊢ h 7 = 3
exact ⟨{0, 1, 2}, hU ▸ Finset.subset_univ _, htri⟩ G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle G⊢ h 7 = 3 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle G⊢ h 7 = 3
have h3 : (3 : ℕ) ∈
{k : ℕ | ∃ G : SimpleGraph (Fin 7), EverySevenHasTriangle G ∧ G.cliqueNum = k} :=
⟨G, hESH, hclique⟩ G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle Gh3:3 ∈ {k | ∃ G, EverySevenHasTriangle G ∧ G.cliqueNum = k}⊢ h 7 = 3
refine le_antisymm (Nat.sInf_le h3) (le_csInf ⟨3, h3⟩ ?_) G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle Gh3:3 ∈ {k | ∃ G, EverySevenHasTriangle G ∧ G.cliqueNum = k}⊢ ∀ b ∈ {k | ∃ G, EverySevenHasTriangle G ∧ G.cliqueNum = k}, 3 ≤ b
rintro k ⟨G', hG', rfl⟩ G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle Gh3:3 ∈ {k | ∃ G, EverySevenHasTriangle G ∧ G.cliqueNum = k}G':SimpleGraph (Fin 7)hG':EverySevenHasTriangle G'⊢ 3 ≤ G'.cliqueNum
obtain ⟨t, -, ht⟩ := hG' Finset.univ (by G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle Gh3:3 ∈ {k | ∃ G, EverySevenHasTriangle G ∧ G.cliqueNum = k}G':SimpleGraph (Fin 7)hG':EverySevenHasTriangle G'⊢ Finset.univ.card = 7 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle Gh3:3 ∈ {k | ∃ G, EverySevenHasTriangle G ∧ G.cliqueNum = k}G':SimpleGraph (Fin 7)hG':EverySevenHasTriangle G't:Finset (Fin 7)ht:G'.IsNClique 3 t⊢ 3 ≤ G'.cliqueNum simp All goals completed! 🐙 G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle Gh3:3 ∈ {k | ∃ G, EverySevenHasTriangle G ∧ G.cliqueNum = k}G':SimpleGraph (Fin 7)hG':EverySevenHasTriangle G't:Finset (Fin 7)ht:G'.IsNClique 3 t⊢ 3 ≤ G'.cliqueNum) G:SimpleGraph (Fin 7) := { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hG:G = { Adj := fun v w ↦ v ≠ w ∧ ↑v < 3 ∧ ↑w < 3, symm := ⋯, loopless := ⋯ }hmem3:∀ (a : Fin 7), a ∈ {0, 1, 2} ↔ ↑a < 3htri:G.IsNClique 3 {0, 1, 2}hclique:G.cliqueNum = 3hESH:EverySevenHasTriangle Gh3:3 ∈ {k | ∃ G, EverySevenHasTriangle G ∧ G.cliqueNum = k}G':SimpleGraph (Fin 7)hG':EverySevenHasTriangle G't:Finset (Fin 7)ht:G'.IsNClique 3 t⊢ 3 ≤ G'.cliqueNum
exact ht.card_eq ▸ ht.isClique.card_le_cliqueNum All goals completed! 🐙Let $h(n)$ be minimal such that every graph on $n$ vertices where every set of $7$ vertices contains a triangle must contain a clique on at least $h(n)$ vertices. Estimate $h(n)$. In particular, do there exist constants $c_1, c_2 > 0$ such that $$n^{1/3+c_1} \ll h(n) \ll n^{1/2-c_2}?$$
The lower half has a positive answer (Erdos813.erdos_813.variants.lower); the upper half is
Erdos813.erdos_813.variants.upper.
@[category research open, question, AMS 5]
theorem erdos_813 :
∃ c₁ > (0 : ℝ), ∃ c₂ > (0 : ℝ),
(fun n : ℕ ↦ (n : ℝ) ^ (1 / 3 + c₁ : ℝ)) =O[atTop] (fun n ↦ (h n : ℝ)) ∧
(fun n : ℕ ↦ (h n : ℝ)) =O[atTop] (fun n : ℕ ↦ (n : ℝ) ^ (1 / 2 - c₂ : ℝ)) := by ⊢ ∃ c₁ > 0,
∃ c₂ > 0,
((fun n ↦ ↑n ^ (1 / 3 + c₁)) =O[atTop] fun n ↦ ↑(h n)) ∧ (fun n ↦ ↑(h n)) =O[atTop] fun n ↦ ↑n ^ (1 / 2 - c₂)
sorry All goals completed! 🐙Erdős and Hajnal proved (see [Er91]) that $$n^{1/3} \ll h(n) \ll n^{1/2}.$$
@[category research solved, AMS 5]
theorem erdos_813.variants.erdos_hajnal :
(fun n : ℕ ↦ (n : ℝ) ^ (1 / 3 : ℝ)) =O[atTop] (fun n ↦ (h n : ℝ)) ∧
(fun n : ℕ ↦ (h n : ℝ)) =O[atTop] (fun n : ℕ ↦ (n : ℝ) ^ (1 / 2 : ℝ)) := by ⊢ ((fun n ↦ ↑n ^ (1 / 3)) =O[atTop] fun n ↦ ↑(h n)) ∧ (fun n ↦ ↑(h n)) =O[atTop] fun n ↦ ↑n ^ (1 / 2)
sorry All goals completed! 🐙Bucić and Sudakov [BuSu23] proved that $h(n) \gg n^{5/12-o(1)}$. Their result is stated for graphs in which every $7$ vertices contain an independent set of size $3$; it applies to $h$ by taking complements.
@[category research solved, AMS 5]
theorem erdos_813.variants.bucic_sudakov :
∀ ε > (0 : ℝ), ∀ᶠ n : ℕ in atTop, (n : ℝ) ^ (5 / 12 - ε : ℝ) ≤ (h n : ℝ) := by ⊢ ∀ ε > 0, ∀ᶠ (n : ℕ) in atTop, ↑n ^ (5 / 12 - ε) ≤ ↑(h n)
sorry All goals completed! 🐙
The lower half of Erdos813.erdos_813 has a positive answer: there is a constant $c_1 > 0$
with $n^{1/3+c_1} \ll h(n)$. This follows from the bound $h(n) \gg n^{5/12-o(1)}$ of Bucić and
Sudakov [BuSu23], since $5/12 > 1/3$.
@[category research solved, question, AMS 5]
theorem erdos_813.variants.lower :
∃ c₁ > (0 : ℝ), (fun n : ℕ ↦ (n : ℝ) ^ (1 / 3 + c₁ : ℝ)) =O[atTop] (fun n ↦ (h n : ℝ)) := by ⊢ ∃ c₁ > 0, (fun n ↦ ↑n ^ (1 / 3 + c₁)) =O[atTop] fun n ↦ ↑(h n)
sorry All goals completed! 🐙
The upper half of Erdos813.erdos_813: is there a constant $c_2 > 0$ with
$h(n) \ll n^{1/2-c_2}$?
@[category research open, question, AMS 5]
theorem erdos_813.variants.upper :
∃ c₂ > (0 : ℝ), (fun n : ℕ ↦ (h n : ℝ)) =O[atTop] (fun n : ℕ ↦ (n : ℝ) ^ (1 / 2 - c₂ : ℝ)) := by ⊢ ∃ c₂ > 0, (fun n ↦ ↑(h n)) =O[atTop] fun n ↦ ↑n ^ (1 / 2 - c₂)
sorry All goals completed! 🐙end Erdos813