Lemma 5.1, p. 14 (Caro–Hansen–Sopena) — every graph with n vertices and m edges has α(G) ≥ max{n²/(n + 2m), (2n − m)/3}
ProvedRecMarkovGraph.IndepLB.lemma_5_1graph-theoryindependence-numberp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1turan
Let be a finite simple graph with vertices and edges, and let be its stability number, the largest size of a set of pairwise non-adjacent vertices. Then
The first bound equals with the average degree; it turns the concentration of the average degree (Theorem 2.2) into the lower bound on .
Differences from the source:
- encoding: any n-vertex graph G with m edges; α(G) → G : SimpleGraph V on a Fintype V, n = Fintype.card V, m = G.edgeFinset.card, α = SimpleGraph.indepNum, all cast to ℝ; reason: the same objects; at n = 0 both sides are 0 (Lean's 0/0 = 0)
Preamble
import Mathlib import Definitions.Def_RecMarkovGraph_IndepLB_Model
Formal statement
namespace RecMarkovGraph.IndepLB
theorem lemma_5_1 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :
max (((Fintype.card V : ℝ)) ^ 2 / ((Fintype.card V : ℝ) + 2 * (G.edgeFinset.card : ℝ)))
((2 * (Fintype.card V : ℝ) - (G.edgeFinset.card : ℝ)) / 3) ≤ (G.indepNum : ℝ) := by sorry
end RecMarkovGraph.IndepLB
Source
Gupte, Zhu, Large independent sets in recursive Markov random graphs, arXiv:2207.04514v4, p. 14, Lemma 5.1 (citing Caro, Hansen, Sopena 2003, Theorems 10 and 11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.