A star–matching pair gives a uniform constant family edge bound
ProvedArexychen.Erdos180.familyFree_edgeCount_le_const_of_star_matching_pairarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be a family of finite simple graphs indexed by a finite nonempty type. Suppose the family contains a member whose reduced graph is a star with at least two edges and a member whose reduced graph is a matching with at least two edges. There is a natural number such that every -free graph on has at most edges, uniformly for all natural . No forest condition is imposed on the other members.
Preamble
import Definitions.Def_arexychen_erdos180_core 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.familyFree_edgeCount_le_const_of_star_matching_pair
{ι : Type v} [Finite ι] [Nonempty ι]
(F : ι → FiniteSimpleGraph.{u})
(hpair : FamilyContainsStarMatchingPair F) :
∃ C : ℕ, ∀ n (G : SimpleGraph (Fin n)), FamilyFree F G → edgeCount G ≤ C := by sorry
Source