Structural constant-or-linear dichotomy for finite forest families
ProvedArexychen.Erdos180.familiesTheoremStructuralarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be a family of finite simple graphs indexed by a finite nonempty type. Suppose every reduced member, obtained by deleting isolated vertices, is acyclic and has at least two edges. Then exactly the following stated alternatives are classified:
where means that the family contains a reduced star with at least two edges and a reduced matching with at least two edges. The asymptotic comparisons are as natural , with real casts. The extremal function forbids ordinary subgraph copies of the original members, including isolated vertices. This is a formalization of the forest/linear regime related to Erdős Problem #180, with no claim of mathematical novelty.
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.DeleteEdges 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.familiesTheoremStructural
{ι : Type v} [Finite ι] [Nonempty ι]
(F : ι → FiniteSimpleGraph.{u})
(hforest : ∀ i : ι, ((F i).reduced).IsAcyclic)
(htwo : ∀ i : ι, (F i).atLeastTwoEdgesAfterDeletingIsolated) :
(FamilyContainsStarMatchingPair F ∧
IsThetaConstant (fun n : ℕ => extremalFamily F n)) ∨
(¬ FamilyContainsStarMatchingPair F ∧
IsThetaLinear (fun n : ℕ => extremalFamily F n)) := by sorry
Source