AFTD Auto-Formalizing Theoretical Domains

conn_set_poly

def

The connected-set generating polynomial Z_G = sum over nonempty vertex sets S inducing a connected subgraph of X^{|S|}.

Statement

open scoped BigOperators Polynomial Classical in
noncomputable def conn_set_poly {V : Type*} [Fintype V] (G : SimpleGraph V) : Polynomial ℝ
Source
step towards op_599_connected_induced_activity_clique_minimum
Verified
28 Oct 2026
Axioms
none listed
Built on 1
  • is_connected_vertex_setA vertex set S of a graph G is connected if the subgraph of G induced by S is connected (in particular S is nonempty).
Used by 1
  • conn_set_poly_QThe defect polynomial Q_G = ((1+X)^n - 1) * Z_G' - n * (1+X)^(n-1) * Z_G, which measures the deviation of the weighted mean order of G…

Lean source view module on GitHub

open scoped BigOperators Polynomial Classical in
/-- Z_G(X) = Σ over connected nonempty S ⊆ V of X^|S|. -/
noncomputable def conn_set_poly {V : Type*} [Fintype V] (G : SimpleGraph V) : Polynomial ℝ := ∑ S ∈ Finset.univ.filter (fun S : Finset V => is_connected_vertex_set G (↑S : Set V)),
    (Polynomial.X : Polynomial ℝ) ^ S.card
See it in the graphDiscuss this resultChallenge it