The generalized Beraha conjecture for non-planar graphs: integer-Q eigenvalue cancellations, limiting curves, and density of flow roots for generalized Petersen graphs

The $Q$-state Potts partition function $Z_G(Q,v)$ specializes to the chromatic polynomial ($v=-1$) and the flow polynomial ($v=-Q$). For planar recursive graph families the accumulation of zeros is governed by the Beraha numbers $B_p=4\cos^2(\pi/p)$, a consequence of Temperley-Lieb and $U_q\mathrm{sl}(2)$ representation theory at roots of unity. Jacobsen and Salas (Nucl. Phys. B 875 (2013) 678) found numerically, for the non-planar generalized Petersen graphs $G(nk,k)$, that a Berker-Kadanoff phase persists and that the non-negative integers replace the Beraha numbers: at integer $Q$ the partition-algebra transfer matrix exhibits massive amplitude vanishings and inclusion-exclusion eigenvalue cancellations. They left open a tightly interlinked cluster of conjectures: the complete eigenvalue decomposition for all widths $k$ (proven only for $k\le6$), the integer-$Q$ reduction of the partition function with its multiplicity function $\rho_k(N)$, a representation-theoretic explanation of the cancellations, the $2k$-branch structure of the flow limiting curves and the density of flow roots of non-planar cubic graphs outside a bounded region, the real-axis dominance patterns with the endpoints $Q_c^{(\Phi)}\approx5.69$ and $Q_c^{(P)}\approx2.861$, and the general 'generalized Beraha conjecture' for non-planar families. The problem is open.

Background

The $Q$-state Potts model on a finite graph $G=(V,E)$ is, in its Fortuin-Kasteleyn (random-cluster) representation, the two-variable polynomial $Z_G(Q,v)=\sum_{E'\subseteq E} v^{|E'|} Q^{k(E')},$ where $v=e^J-1$ is a temperature-like parameter ($J$ being the exchange coupling) and $k(E')$ is the number of connected components of the spanning subgraph $(V,E')$; after a change of variables this is the Tutte polynomial of graph theory. Two specializations are central here. The chromatic polynomial $P_G(Q)=Z_G(Q,-1)$ counts proper $Q$-colorings of the vertices when $Q$ is a positive integer. The flow polynomial $\Phi_G(Q)=(-1)^{|E|}Q^{-|V|}Z_G(Q,-Q)$ counts nowhere-zero $\mathbb{Z}_Q$-flows: assignments of nonzero group elements to the edges of an oriented graph that are conserved at every vertex (a Kirchhoff-type condition). For planar graphs, Potts duality $vv^*=Q$ exchanges the two: $P_{G^*}(Q)=Q\,\Phi_G(Q)$.

The generalized Petersen graph $G(m,k)$ has $2m$ vertices $\{u_i,v_i\}_{i=1}^m$ and edges $u_iu_{i+1}$ (an outer cycle, indices modulo $m$), $v_iv_{i+k}$ (inner star polygons), and spokes $u_iv_i$; $G(5,2)$ is the Petersen graph, and for $k\ge2$ these graphs are generically non-planar. Fixing $k$ and setting $m=nk$ gives a recursive non-planar family: $G(nk,k)$ can be drawn as $n$ identical layers of $2k$ vertices (width $L=k+1$) with periodic boundary conditions in the longitudinal direction.

For layered families the partition function is computed by a transfer matrix $T_L$ acting on connectivity states, that is, on set partitions of $\{0,1,\ldots,k,0',1',\ldots,k'\}$; a block of a partition meeting both rows is called a link, and $\ell$ denotes the number of links. Because the transfer matrix never increases $\ell$, the partition function decomposes as $Z_{G(nk,k)}=\sum_{\ell,\lambda}\alpha_{\ell,\lambda}\operatorname{tr}(T_{k+1,\ell,\lambda})^n$ over blocks labeled by $\ell$ and by irreducible representations $\lambda$ of the symmetric group $S_\ell$. The amplitudes $\alpha_{\ell,\lambda}$ are explicit polynomials in $Q$ coming from the representation theory of the partition algebra (Halverson and Ram) — the algebra of join and detach operators on set partitions, which plays for non-planar transfer matrices the role that the Temperley-Lieb algebra (the diagram algebra of non-crossing connectivities) plays for planar ones.

When a partition function is a finite sum of exponentials $\sum_i \alpha_i\mu_i^n$, the Beraha-Kahane-Weiss (BKW) theorem of Beraha, Kahane and Weiss describes the accumulation set of its zeros as $n\to\infty$: it consists of the points where a unique dominant (largest-modulus) eigenvalue has vanishing amplitude — isolated limiting points — together with the curves where two or more eigenvalues are equimodular — the limiting curves $\mathcal B$.

For two-dimensional (planar) Potts models the antiferromagnetic regime contains a massless intermediate phase, the Berker-Kadanoff (BK) phase, and when a temperature curve $v(Q)$ crosses this phase the real accumulation points of chromatic zeros are the Beraha numbers $B_p=4\cos^2(\pi/p)$: odd-index $B_p$ appear as isolated limiting points and even-index $B_p$ lie on the limiting curves, up to a family-dependent endpoint $Q_c$. This planar picture follows from the representation theory of the Temperley-Lieb algebra and the quantum group $U_q\mathrm{sl}(2)$ (a one-parameter deformation of the Lie algebra $\mathrm{sl}(2)$, with $Q=4\cos^2(\pi/p)$ when the deformation parameter is the root of unity $q=e^{i\pi/p}$) at roots of unity, where $Q=B_p$ forces massive degeneracies and inclusion-exclusion eigenvalue cancellations independent of $v$; it has been verified exactly for cyclic strips of the square and triangular lattices. On the density side, Sokal proved that chromatic roots of all graphs are dense in the whole complex plane, whence, by planar duality, the same holds for flow roots of planar graphs.

The immediate predecessor of the source paper is the companion study by Jacobsen and Salas of the flow polynomial of the same family. Welsh conjectured that $\Phi_G$ has no real roots on $(4,\infty)$; Haggard, Pearce and Royle refuted this with the generalized Petersen graph $G(16,6)$ (real flow roots near $4.025$ and $4.233$) and conjectured instead the absence of roots on $[5,\infty)$. Jacobsen and Salas refuted that variant in turn by showing that $Q=5$ is an isolated accumulation point of real flow roots along the families $G(6n,6)$ and $G(7n,7)$, with a further accumulation point at $Q\approx5.235261$, and they proposed the still-open conjecture $\Phi_G(Q)>0$ on $[6,\infty)$.

The source paper (Jacobsen and Salas, Nucl. Phys. B 875 (2013) 678) extended this to the full partition function $Z_{G(nk,k)}(Q,v)$ for $1\le k\le7$. Its findings — numerical, or symbolic for small $k$ only — are: (i) a BK phase exists for this non-planar family, with the same qualitative features as in two dimensions; (ii) the role played by the Beraha numbers for planar graphs is played by the non-negative integers, in that at each integer $Q$ there are massive amplitude vanishings and inclusion-exclusion eigenvalue cancellations exactly analogous to those at Beraha numbers in the planar case; (iii) the partition function admits a 'complete' decomposition (their Eqs. (3.6)/(3.9)) into pairwise-distinct eigenvalues, proven symbolically for $1\le k\le6$ (with $6,20,113,755,5568,43975$ distinct eigenvalues for $k=1,\ldots,6$) and conjectured for all $k\ge7$; (iv) at each non-negative integer $Q=N\le4$ the partition function collapses to a short finite sum of sector 'characters' plus a trivial-eigenvalue term $\rho_k(N)v^{2nk}$, conjectured for all $N$ and all $k\ge N$ (their Conjecture 5.1); (v) the flow limiting curves $\mathcal B_k$ have exactly $2k$ outward branches, while the chromatic curves are bounded, crossing the real axis at $Q_c^{(P)}(k)$ with $Q_c^{(P)}(k)\to2.861\pm0.003$, and $Q_c^{(\Phi)}(k)\to5.69\pm0.01$; and (vi) the title's generalized Beraha conjecture (their Conjecture 8.3): for general non-planar layered families, along curves $v(Q)$ inside the non-planar BK region, the type-(a) and type-(b) real limiting points are the odd and even non-negative integers up to $Q_c(L)$. The authors state that no systematic study connects these integer-$Q$ cancellations to the representation theory of the partition algebra, and they observe regions where a complex-conjugate pair of eigenvalues is dominant — which, by the BKW mechanism, should carry two-dimensional accumulation of zeros, a phenomenon absent from all previously studied families — without any criterion for its occurrence.

Problem Statement

The problem is to replace this empirical picture by rigorous mathematics — or to refute it. The common scientific objective is to establish the integer-replacement mechanism: that for non-planar recursive graph families the non-negative integers play exactly the role that the Beraha numbers play for planar families, in the transfer-matrix spectrum, in the structure of the zero-accumulation sets, and in the flow and chromatic limiting curves. The source's interrelated deliverables are the following. Items 1, 2 and 4-7 are propositions, each independently standing and each to be proved in the stated generality or refuted by an explicit counterexample; item 3 asks for the mechanism behind the amplitude vanishings and eigenvalue cancellations of items 1 and 2, and is complete once it accounts for every such integer-$Q$ vanishing and cancellation, with no unexplained case. Proving or refuting any single component resolves that component; the remaining components stay open.

1. Complete decomposition (source Eqs. (3.6)/(3.9)). Prove or disprove that for every $k\ge1$ the partition function of $G(nk,k)$ can be written as $Z_{G(nk,k)}(Q,v)=\sum_{\ell=0}^{k-1}\sum_{\lambda\in S_\ell}\alpha_{\ell,\lambda}\,\operatorname{tr}\big(T^{(nt)}_{k+1,\ell,\lambda}\big)^{n}+\beta_k\,\operatorname{tr}\big(T^{(nt)}_{k+1,k}\big)^{n}+\gamma_{k+1}\,v^{2nk},$ where the reduced block $T^{(nt)}_{k+1,k}$ contains exactly $2k+1$ non-trivial eigenvalues and all eigenvalues appearing on the right-hand side (including the trivial eigenvalue $v^{2k}$) are pairwise distinct. This is proven symbolically for $1\le k\le6$; the claim is that it holds for all $k\ge7$.

2. Integer-$Q$ reduction (source Conjecture 5.1). Prove or disprove that for every non-negative integer $N$ and every $k\ge N$, $Z_{G(nk,k)}(N,v)=\sum_{\ell=0}^{N-2}\ \left[\sum_{\substack{\lambda\in S_\ell\\ \alpha_{\ell,\lambda}(N)>0}}\alpha_{\ell,\lambda}(N)\,\chi_{k,\ell,\lambda}\right]+\chi_{k,N-1,(1)^{N-1}}+\rho_k(N)\,v^{2nk},$ where the characters $\chi_{k,\ell,\lambda}$ are the net sums of $n$-th powers of the non-trivial eigenvalues of sector $(\ell,\lambda)$ that survive the cancellations at $Q=N$. Determine the function $\rho_k(N)$ (currently known only for $0\le N\le4$: $\rho_k(N)=0$ for $N\le3$, and $\rho_k(4)=6$ for even $k$, $0$ for odd $k$) and the multiplicity patterns of the trivial eigenvalue, and establish the sum rule $\sum_{\ell=0}^{N-1}\sum_{\lambda}\alpha_{\ell,\lambda}(N)\,\widetilde N_k(\ell,\lambda)+\rho_k(N)=N^{k+1}$, where $\widetilde N_k(\ell,\lambda)$ is the number of contributing non-trivial eigenvalues from sector $(\ell,\lambda)$.

3. Mechanism. Provide a representation-theoretic explanation, within the partition-algebra framework governing the non-planar transfer matrix ($S_\ell$ sectors and amplitudes $\alpha_{\ell,\lambda}$), of the amplitude vanishings and inclusion-exclusion eigenvalue cancellations at non-negative integer $Q$ — the non-planar counterpart of the $U_q\mathrm{sl}(2)$/Temperley-Lieb degeneracies at the Beraha numbers.

4. Flow limiting curves (source Conjecture 6.1). Prove or disprove that, for each fixed $k\ge1$, the limiting curve $\mathcal B_k$ of the flow-polynomial zeros has exactly $2k$ outward branches extending to $Q=\infty$ with asymptotic angles $\arg Q=\theta_{k,j}=(j-\tfrac12)\pi/k$ for $j=1,\ldots,2k$, with the conjectured alternation of the dominant eigenvalues $\mu_{k+1,0}^{\star}$ and $\mu_{k+1,1,(1)}^{\star}$ between adjacent asymptotic sectors; and prove or disprove the associated density statement: as $k\to\infty$ the accumulation points of the flow zeros of $G(nk,k)$ become dense in the whole complex $Q$-plane outside the limiting curve $\mathcal B_\infty$ — in particular, that the flow roots of non-planar cubic graphs are dense in the complex plane outside some bounded region.

5. Real-axis structure and endpoints (source Conjectures 6.2 and 7.1). Prove or disprove the conjectured dominant-eigenvalue patterns on the real $Q$-axis: for the flow polynomial ($k\ge4$), $\mu_{k+1,1,(1)}^{\star}$ on $\operatorname{Re}Q\in(-\infty,2]$, $\mu_{k+1,2,(2)}^{\star}$ on $[2,4]$, $\mu_{k+1,3,(3)}^{\star}$ on $[4,Q_c^{(\Phi)}(k)]$, and then $\mu_{k+1,1,(1)}^{\star}$ for even $k$ or $\mu_{k+1,0}^{\star}$ for odd $k$ on $[Q_c^{(\Phi)}(k),\infty)$, so that $Q=1,3,5$ are isolated limiting points ($Q=5$ only when $Q_c^{(\Phi)}(k)>5$) and $Q=2,4,Q_c^{(\Phi)}(k)$ are non-isolated ones; and the analogous chromatic pattern ($k\ge3$), with $Q=1$ isolated and $Q=0,2,Q_c^{(P)}(k)$ non-isolated. Establish rigorously the existence and the values of $Q_c^{(\Phi)}(k)$, $Q_c^{(P)}(k)$ and of their infinite-width limits $\lim_{k\to\infty}Q_c^{(\Phi)}(k)$ and $\lim_{k\to\infty}Q_c^{(P)}(k)$ (numerically $5.69\pm0.01$ and $2.861\pm0.003$).

6. General statement (source Conjecture 8.3, the generalized Beraha conjecture). Prove or disprove: for a family $G_{n,L}$ of non-planar connected graphs consisting of $n$ identical layers of width $L$ with periodic boundary conditions in the $n$-direction, there exist curves $v_\pm(Q)$ (with $v_+(0)=0$) and a value $Q_0$, possibly $Q_0=\infty$, such that along any smooth curve $v(Q)$ with $v_-(Q)\le v(Q)\le v_+(Q)$ and $Q\in[0,Q_0]$, the real parts of the type-(a) limiting set (the isolated limiting points, where a unique dominant eigenvalue has vanishing amplitude) and the type-(b) limiting set (the points on the equimodular limiting curves) of partition-function zeros are the odd integers $(2\mathbb{N}-1)\cap[0,Q_c(L))$ and the even integers $2\mathbb{N}\cap[0,Q_c(L)]\cup\{Q_c(L)\}$ respectively (with the source's caveat that, for some curves $v(Q)$, the value $0$ might not be present in the type-(b) set), and for each $p\in\mathbb{N}$ the dominant eigenvalue for $\operatorname{Re}Q\in(2(p-1),2p)\cap[0,Q_c(L))$ comes from the fully symmetric representation $(p)$ of the sector with $p$ marked clusters (the source's general-$L$ sector label, playing the role of the link number $\ell$ in items 1 and 2).

7. Two-dimensional accumulation. Characterize analytically the regions of the $(Q,v)$ plane in which a complex-conjugate pair of transfer-matrix eigenvalues is dominant — for the Petersen family, in the chromatic case, the two small complex-conjugate regions on the rightmost part of the limiting curve $\mathcal B_k$ for odd $k$, conjectured in the source to disappear as $k\to\infty$ — and prove that these regions indeed carry two-dimensional accumulation of partition-function zeros, as the BKW mechanism predicts.

References

1. J. L. Jacobsen and J. Salas, "A generalized Beraha conjecture for non-planar graphs", Nuclear Physics B 875 (2013) 678-718. DOI: 10.1016/j.nuclphysb.2013.07.012; arXiv:1303.5210. https://arxiv.org/abs/1303.5210
2. J. L. Jacobsen and J. Salas, "Is the five-flow conjecture almost false?", Journal of Combinatorial Theory, Series B 103 (2013) 532-565. DOI: 10.1016/j.jctb.2013.06.001; arXiv:1009.4062. https://arxiv.org/abs/1009.4062
3. F. Dong, "A survey on the study of real zeros of flow polynomials", Journal of Graph Theory 92 (2019) 361-376. DOI: 10.1002/jgt.22458; arXiv:2007.05195. https://arxiv.org/abs/2007.05195
4. S. Ok and T. J. Perrett, "Density of Real Zeros of the Tutte Polynomial", Combinatorics, Probability and Computing 27 (2018) 398-410. DOI: 10.1017/S0963548318000019; arXiv:1608.08747. https://arxiv.org/abs/1608.08747
5. T. J. Perrett and C. Thomassen, "Density of Chromatic Roots in Minor-Closed Graph Families", Combinatorics, Probability and Computing 27 (2018) 988-998. DOI: 10.1017/S0963548318000184. https://doi.org/10.1017/S0963548318000184
6. J. Brown and P. T. Otto, "A generalization of the Beraha-Kahane-Weiss theorem with graph polynomial applications", Contributions to Discrete Mathematics 20 (2025) 384-395. DOI: 10.55016/ojs/cdm.v20i2.76682; arXiv:2008.01784. https://arxiv.org/abs/2008.01784
7. A. D. Sokal, "Chromatic roots are dense in the whole complex plane", Combinatorics, Probability and Computing 13 (2004) 221-261. DOI: 10.1017/S0963548303006023; arXiv:cond-mat/0012369. https://arxiv.org/abs/cond-mat/0012369
8. S. Beraha, J. Kahane and N. J. Weiss, "Limits of chromatic zeros of some families of maps", Journal of Combinatorial Theory, Series B 28 (1980) 52-65. DOI: 10.1016/0095-8956(80)90055-6. https://doi.org/10.1016/0095-8956(80)90055-6
9. T. Halverson and A. Ram, "Partition Algebras", European Journal of Combinatorics 26 (2005) 869-921. DOI: 10.1016/j.ejc.2004.06.005; arXiv:math/0401314. https://arxiv.org/abs/math/0401314
10. G. Haggard, D. J. Pearce and G. F. Royle, "Computing Tutte Polynomials", ACM Transactions on Mathematical Software 37 (2010), Article 24. DOI: 10.1145/1824801.1824802. https://doi.org/10.1145/1824801.1824802
11. Z. Bajnok, J. L. Jacobsen, Y. Jiang, R. I. Nepomechie and Y. Zhang, "Cylinder partition function of the 6-vertex model from algebraic geometry", Journal of High Energy Physics 2020 (2020), Article 169. DOI: 10.1007/JHEP06(2020)169; arXiv:2002.09019. https://arxiv.org/abs/2002.09019
12. J. L. Jacobsen, Y. Jiang and Y. Zhang, "Torus partition function of the six-vertex model from algebraic geometry", Journal of High Energy Physics 2019 (2019), Article 152. DOI: 10.1007/JHEP03(2019)152; arXiv:1812.00447. https://arxiv.org/abs/1812.00447
13. C. McPhail-Snyder and K. A. Miller, "Planar diagrams for local invariants of graphs in surfaces", Journal of Knot Theory and Its Ramifications 29 (2020) 1950093. DOI: 10.1142/S0218216519500937; arXiv:1805.00575. https://arxiv.org/abs/1805.00575
14. J. L. Jacobsen, J. Salas and C. R. Scullard, "Phase diagram of the triangular-lattice Potts antiferromagnet", Journal of Physics A: Mathematical and Theoretical 50 (2017) 345002. DOI: 10.1088/1751-8121/aa778f; arXiv:1702.02006. https://arxiv.org/abs/1702.02006
15. J. L. Jacobsen, "High-precision percolation thresholds and Potts-model critical manifolds from graph polynomials", Journal of Physics A: Mathematical and Theoretical 47 (2014) 135001. DOI: 10.1088/1751-8113/47/13/135001; arXiv:1401.7847. https://arxiv.org/abs/1401.7847
16. J. Allagan, V. Voloshin, V. Deriglazov and R. N. Lopez-Bonilla, "Explicit Equimodular Curves for Prism-Graph Chromatic Polynomials and the Beraha-Kahane-Weiss Limit Set", American Journal of Computational Mathematics 16 (2026) 14-26. DOI: 10.4236/ajcm.2026.161002. https://doi.org/10.4236/ajcm.2026.161002