A uniform linear edge bound for a forbidden reduced forest
ProvedArexychen.Erdos180.edgeCount_le_of_isHFree_of_deleteIsolated_isAcyclicarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Fix a finite simple graph . If the graph induced by its non-isolated vertices is acyclic, there is a natural number such that every finite simple graph with decidable adjacency satisfies
The constant is chosen before the host vertex type and host graph. Freeness forbids an injective edge-preserving copy of the whole original graph , including its isolated vertices.
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.edgeCount_le_of_isHFree_of_deleteIsolated_isAcyclic
{α : Type u} [Fintype α] (H : SimpleGraph α)
(hforest : (deleteIsolated H).IsAcyclic) :
∃ C : ℕ, ∀ (β : Type v) [Fintype β] (G : SimpleGraph β)
[DecidableRel G.Adj],
IsHFree H G → edgeCount G ≤ C * Fintype.card β := by sorry
Source