Sharp linear lower bound on the triangular thickness of `Kₙ`.
ProvedTriangularForest.triangularThickness_lower_bound_sharpaether-cataloglogic
Sharp linear lower bound on the triangular thickness of Kₙ. Covering the edges of Kₙ
(n ≥ 2) by k triangular forests forces n ≤ 3k. This improves
TriangularForest.triangularThickness_lower_bound (n - 1 ≤ 4k) by feeding the sharp sparsity
bound 2e ≤ 3(n-1) into the counting argument, and by sparsity_bound_attained the sparsity
input can no longer be improved.
theorem TriangularForest.triangularThickness_lower_bound_sharp{n k : ℕ} (hn : 2 ≤ n)
(H : Fin k → SimpleGraph (Fin n)) [∀ i, DecidableRel (H i).Adj]
(hTF : ∀ i, IsTriangularForest (H i))
(hcov : ∀ x y : Fin n, x ≠ y → ∃ i, (H i).Adj x y) :
n ≤ 3 * k := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Logic/TriangularForest/Extremal.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Logic/TriangularForest/Extremal.lean
import Mathlib
import Definitions.Def_Logic_TriangularForest_Complexity
import Definitions.Def_Logic_TriangularForest_Defs
import Definitions.Def_Logic_TriangularForest_Extremal
/-!
# The sparsity bound is attained for every odd order
`TriangularForest.two_mul_card_edgeFinset_le` says that a triangular forest on `n ≥ 1` vertices
satisfies `2e ≤ 3(n-1)`. Here we show that this is *sharp for every odd `n`*, by exhibiting the
friendship (windmill) graphs `Fₖ`: `k` triangles glued at a common centre.
* `TriangularForest.isTriangularForest_of_unique_far_neighbour` — a structural membership
criterion: if every vertex other than a fixed vertex `x` has at most one neighbour besides
`x`, then the graph is a triangular forest. This is the "windmill" criterion, and it is proved
by a rotation argument on cycles rather than by a finite check;
* `TriangularForest.fan` — the friendship graph `Fₖ` on `2k+1` vertices;
* `TriangularForest.isTriangularForest_fan` — `Fₖ` is a triangular forest;
* `TriangularForest.card_edgeFinset_fan` — `Fₖ` has exactly `3k` edges;
* `TriangularForest.sparsity_bound_attained` — hence `2e = 3(n-1)` for `n = 2k+1`: the bound of
`two_mul_card_edgeFinset_le` cannot be improved for any odd order.
-/
open TriangularForest
open SimpleGraph Finset
variable {V : Type*} {G : SimpleGraph V}Formal statement
theorem TriangularForest.triangularThickness_lower_bound_sharp{n k : ℕ} (hn : 2 ≤ n)
(H : Fin k → SimpleGraph (Fin n)) [∀ i, DecidableRel (H i).Adj]
(hTF : ∀ i, IsTriangularForest (H i))
(hcov : ∀ x y : Fin n, x ≠ y → ∃ i, (H i).Adj x y) :
n ≤ 3 * k := by sorrySource