The extremal function of a reduced forest is
ProvedArexychen.Erdos180.isOLinear_extremalNumber_of_deleteIsolated_isAcyclicarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
For a finite simple graph whose induced graph on non-isolated vertices is acyclic, the function is as natural tends to infinity. The extremal value is the natural-number supremum of edge counts of -free graphs on , using ordinary subgraph containment of the whole . The asymptotic comparison casts these values and to real numbers.
Preamble
import Definitions.Def_arexychen_erdos180_core 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.isOLinear_extremalNumber_of_deleteIsolated_isAcyclic
{α : Type u} [Fintype α] (H : SimpleGraph α)
(hforest : (deleteIsolated H).IsAcyclic) :
IsOLinear (fun n => extremalNumber H n) := by sorry
Source