AFTD Auto-Formalizing Theoretical Domains

greedy_indep_var

def

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
See it in the graphDiscuss this resultChallenge it