Partition functions and a generalized coloring-flow duality for embedded graphs

Abstract

Let $G$ be a finite group and $\chi :G\to \mathbb{C}$ a class function. Let $H=(V,E)$ be a directed graph with for each vertex a cyclic order of the edges incident to it. The cyclic orders give a collection $F$ of faces of $H$. Define the partition function $P_{\chi }(H):={\sum }_{\kappa :E\to G}{\prod }_{v\in V}\chi (\kappa (\delta (v)))$, where $\kappa (\delta (v))$ denotes the product of the $\kappa$-values of the edges incident with $v$ (in order), where the inverse is taken for any edge leaving $v$. Write $\chi ={\sum }_{\lambda }{m}_{\lambda }{\chi }_{\lambda }$, where the sum runs over irreducible representations $\lambda$ of $G$ with character ${\chi }_{\lambda }$ and with $m_{\lambda }\in \mathbb{C}$ for every $\lambda$. If $H$ is connected, it is proved that $P_{\chi }(H)=|G{|}^{|E|}{\sum }_{\lambda }{\chi }_{\lambda }(1{)}^{|F|-|E|}{m}_{\lambda }^{|V|}$, where $1$ is the identity element of $G$. Among the corollaries, a formula for the number of nowhere-identity $G$-flows on $H$ is derived, generalizing a result of Tutte. We show that these flows correspond bijectively to certain proper $G$-colorings of a covering graph of the dual graph of $H$. This correspondence generalizes coloring-flow duality for planar graphs.

Based on comments of the referees, some revisions have been made. 13 pages. To appear in Journal of Graph Theory