A reduced forest with at least two edges has linear extremal growth
ProvedArexychen.Erdos180.isThetaLinear_extremal_of_reduced_isAcyclic_of_atLeastTwoarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be a finite simple graph whose induced graph on non-isolated vertices is acyclic and has at least two edges. Its extremal function for ordinary subgraph freeness of the original satisfies
The comparison is at the natural-number at-top filter after casting the extremal values and to real numbers; it gives eventual positive constant upper and lower linear bounds.
Preamble
import Definitions.Def_arexychen_erdos180_core 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 attribute [local instance] SimpleGraph.neighborSetFintype universe u v open Arexychen.Erdos180
Formal statement
theorem Arexychen.Erdos180.isThetaLinear_extremal_of_reduced_isAcyclic_of_atLeastTwo
(H : FiniteSimpleGraph.{u})
(hforest : H.reduced.IsAcyclic)
(htwo : H.atLeastTwoEdgesAfterDeletingIsolated) :
IsThetaLinear (fun n => H.extremal n) := by sorry
Source