Mixed partition functions are exactly the graph parameters of exponentially bounded edge-connection rank

Abstract

We prove a conjecture of Regts and Sevenster: a complex-valued graph parameter $f$ with $f(\varnothing )=1$ has exponentially bounded edge-connection rank if and only if it is a mixed partition function; moreover, the model may be chosen with its numbers of even and odd colours explicitly bounded in terms of the rank bound. From $f$ we construct a connection category, a rigid symmetric $\mathbb{C}$-linear monoidal category whose morphism spaces have the connection ranks as dimensions and whose trace pairings are nondegenerate. The rank hypothesis forces moderate tensor growth, and a recent theorem of Etingof and Penneys then shows that every nilpotent endomorphism has trace zero; together with the nondegeneracy of the trace pairing, this makes the category semisimple, and a theorem of Deligne provides a faithful symmetric tensor functor to finite-dimensional super vector spaces. We then identify the resulting super tensor network with the Regts-Sevenster model exactly, viz. with its Eulerian-subgraph expansion and its sign of $-1$ for every fermionic circuit. An appendix gives an independent and direct proof of the nilpotent-trace step, showing that in a rigid symmetric $\mathbb{C}$-linear category with $\mathrm{End}(1)=\mathbb{C}$, exponentially bounded endomorphism growth makes the trace zeta function of every endomorphism rational, with explicit degree bounds.

Formalization now assumption-free (Deligne's theorem proved in the development); minor clarifications in Sections 1, 4.8 and 5.4

Topics & keywords