AFTD Auto-Formalizing Theoretical Domains

simple_graph_clique_polynomial

def

The clique polynomial $C_G(z) = \sum_{t=0}^{|V|} c_t(G) z^t$ of a finite simple graph $G$, where $c_t(G)$ is the number of cliques of order $t$ in $G$.

Statement

noncomputable def simple_graph_clique_polynomial {V : Type*} [Fintype V] (G : SimpleGraph V) : Polynomial ℤ
Defined in
arXiv:2611.14430, Section 4
Verified
11 Nov 2026
Axioms
none listed
Used by 1
  • simple_graph_qThe invariant $q(G) = C_G(-1)$ of a finite simple graph $G$, obtained by evaluating its clique polynomial at $-1$.

Read back from the Lean

Given a finite type V and a simple graph G on V, simple_graph_clique_polynomial G is the polynomial in Polynomial ℤ defined as the sum over t from 0 to Fintype.card V of c_t * X^t, where c_t is the number of cliques of size t in G ((G.cliqueFinset t).card), cast to ℤ.

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

/-- The clique polynomial of a finite simple graph, with coefficient of z^t equal to the number of cliques of size t. -/
noncomputable def simple_graph_clique_polynomial {V : Type*} [Fintype V] (G : SimpleGraph V) : Polynomial ℤ :=
  open scoped Classical in
  ∑ t ∈ Finset.range (Fintype.card V + 1), Polynomial.C ((G.cliqueFinset t).card : ℤ) * Polynomial.X ^ t
See it in the graphDiscuss this resultChallenge it