A matching construction gives an eventual lower bound
ProvedArexychen.Erdos180.matchingConstruction_extremalFamily_eventually_half_learexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be a family of finite simple graphs indexed by a finite nonempty type. Assume every member has at least two edges after deleting isolated vertices, and no reduced member has at most one neighbor per vertex. Then, for all sufficiently large natural ,
The two-edge hypothesis is retained as a binder even though the source proof does not use it.
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.matchingConstruction_extremalFamily_eventually_half_le
{ι : Type v} [Finite ι] [Nonempty ι]
(F : ι → FiniteSimpleGraph.{u})
(_hTwo : ∀ i : ι, (F i).atLeastTwoEdgesAfterDeletingIsolated)
(hNoMatching : ∀ i : ι, ¬ (F i).matchingAfterDeletingIsolated) :
∀ᶠ n in atTop, n / 2 ≤ extremalFamily F n := by sorry
Source