greedy_indep_var
The variance of the cardinality of the random greedy maximal independent set of a finite simple graph on vertex set Fin n under the uniform distribution over vertex inspection orderings.
Statement
open Classical in noncomputable def greedy_indep_var {n : ℕ} (G : SimpleGraph (Fin n)) : ℝ
- Defined in
- arXiv:2609.14826: Section 2
- Verified
- 10 Nov 2026
- Axioms
- none listed
Read back from the Lean
For a natural number n and a simple graph G on the vertex type Fin n, greedy_indep_var G is the real number defined as the variance of the size of the greedy independent set under a uniformly random permutation of the vertices. Specifically:
- For each permutation σ of Fin n, vertices are processed in the order σ(0), σ(1), ..., σ(n-1), starting with the empty set and adding vertex v to the set if and only if no vertex already in the set is adjacent in G to v.
- X(σ) is the cardinality of the resulting independent set.
- E1 is the average (mean) of X(σ) over all n! permutations σ of Fin n.
- E2 is the average of (X(σ))^2 over all n! permutations σ of Fin n.
- The definition evaluates to E2 - E1^2 (the variance of X).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
open Classical in /-- Variance of the random greedy independent set size on a graph on Fin n. -/ noncomputable def greedy_indep_var {n : ℕ} (G : SimpleGraph (Fin n)) : ℝ := let greedy_indep : Equiv.Perm (Fin n) → Finset (Fin n) := fun σ => (List.ofFn σ).foldl (fun I v => if ∀ u ∈ I, ¬G.Adj u v then insert v I else I) ∅ let N : ℝ := (Nat.factorial n : ℝ) let X : Equiv.Perm (Fin n) → ℝ := fun σ => ((greedy_indep σ).card : ℝ) let E1 : ℝ := (∑ σ, X σ) / N let E2 : ℝ := (∑ σ, (X σ) ^ 2) / N E2 - E1 ^ 2