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