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

Autor: Bart Sevenster, Bart Litjens
Přispěvatelé: Algebra, Geometry & Mathematical Physics (KDV, FNWI)
Rok vydání: 2017
Předmět:
Zdroj: Journal of Graph Theory, 88(2), 271-283. Wiley-Liss Inc.
ISSN: 0364-9024
DOI: 10.48550/arxiv.1701.00420
Popis: Let $G$ be a finite group and $\chi: G \rightarrow \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 \rightarrow 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.
Comment: Based on comments of the referees, some revisions have been made. 13 pages. To appear in Journal of Graph Theory
Databáze: OpenAIRE
Externí odkaz: