A star construction gives an eventual lower bound
ProvedArexychen.Erdos180.starConstruction_extremalFamily_eventually_pred_learexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be a family of finite simple graphs indexed by a finite nonempty type. Suppose every member has at least two edges after deleting isolated vertices, and none of the reduced members is a star. Then, for all sufficiently large natural ,
Subtraction is natural-number subtraction, and freeness concerns the original forbidden graphs.
Preamble
import Definitions.Def_arexychen_erdos180_families_bounds import Definitions.Def_arexychen_erdos180_finite import Mathlib.Analysis.Asymptotics.Theta import Mathlib.Combinatorics.SimpleGraph.Acyclic import Mathlib.Combinatorics.SimpleGraph.Basic import Mathlib.Combinatorics.SimpleGraph.Finite import Mathlib.Combinatorics.SimpleGraph.Maps import Mathlib.Combinatorics.SimpleGraph.Matching import Mathlib.Combinatorics.SimpleGraph.Subgraph import Mathlib.Tactic open Filter open Asymptotics universe u v w open Arexychen.Erdos180
Formal statement
theorem Arexychen.Erdos180.starConstruction_extremalFamily_eventually_pred_le
{ι : Type v} [Finite ι] [Nonempty ι]
(F : ι → FiniteSimpleGraph.{u})
(hTwo : ∀ i : ι, (F i).atLeastTwoEdgesAfterDeletingIsolated)
(hNoStar : ∀ i : ι, ¬ (F i).starAfterDeletingIsolated) :
∀ᶠ n in atTop, n - 1 ≤ extremalFamily F n := by sorry
Source