Transfer Operators and Independence Polynomials for Strong Powers of Circulant Graphs
Todd Hildebrant · 2026
Read Transfer Operators and Independence Polynomials for Strong Powers of Circulant Graphs by Todd Hildebrant (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-14416.txt.
Introduction
Hildebrant studies independent sets of strong powers of circulant graphs via transfer matrices. Compatibility splits into within-layer and between-layer parts, giving a dihedral transfer operator. Its polynomial factors into an anomalous part from the trivial component and a cyclotomic part from other Fourier modes. The spectral radius sits in the trivial part, so growth is ruled by a low-dimensional compact operator. Independence polynomials come out exactly for strong cylinders and tori, with only a sparse high-weight cyclotomic correction, checked on the seven-cycle case.
Catalog record
| CREATOR | Todd Hildebrant |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19717 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.14416
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Transfer Operators and Independence Polynomials for Strong Powers of Circulant Graphs Todd Hildebrant Abstract . We study independent sets in strong powers of circulant graphs using a transfer matrix formulation. The compatibility constraints separate into intra-layer and inter-layer components, yielding a transfer operator that is equivariant under the dihedral group action. The characteristic polynomial of the transfer operator factors into an anomalous component (arising from the trivial isotypic component, with rational coefficients) and a cyclotomic component (arising from nontrivial Fourier modes, splitting over the maximal real cyclotomic subfield). We show that the spectral radius is attained in the trivial isotypic component, so the dominant exponential growth is governed by a low-dimensional orbit-compressed operator. The independence polynomial is computed exactly for strong cylinders and tori, with the cyclotomic sector contributing a sparse correction confined to high-weight coefficients. All results are verified for C 7 C_{7} . 1. Introduction Let G be a graph. The Shannon capacity \Theta(G)=\lim_{d\to\infty}\alpha(G^{\boxtimes d})^{1/d} is one of the central invariants in zero-error information theory. Even for simple families such as odd cycles, determining \Theta(G) remains open. For circulant graphs G=\Cay(\mathbb{Z}_{n},C) , the adjacency matrix of G^{\boxtimes d} is block circulant with circulant blocks (BCCB) and diagonalizes via the tensor Fourier transform, yielding spectral bounds such as the Lovász theta function \vartheta(G) . These bounds are tight for even cycles and the Paley graph P(5)=C_{5} , but for n\geq 7 odd, the gap between \vartheta(C_{n}) and the best known constructions remains unresolved. We use the term \Cay to denote Cayley graphs, and C_{n} to denote the cycle graph on n vertices where it is clear from context, however the results apply to any circulant graph with symmetric connection set, which are also Cayley graphs of \mathbb{Z}_{n} . In this paper we develop a complementary approach based on transfer matrices. The independence constraints factor into intra-layer and inter-layer components, giving a transfer operator on the independent sets of the base graph. This operator is equivariant under the dihedral action, leading to a block decomposition whose spectral structure we analyze in detail. Our main results are: (1) The transfer operator admits a dihedral-equivariant block decomposition whose characteristic polynomial factors according to the isotypic components (Theorem 6.1 ). (2) The spectral radius lies in the trivial isotypic component, reducing the dominant growth to a finite-dimensional computation (Theorem 5.1 ). (3) For the cycle graph C_{7} , the orbit-compressed transfer matrix is 5\times 5 , and the anomalous factor is an irreducible quartic with Galois group S_{4} , whose splitting field is disjoint from \mathbb{Q}(\cos(2\pi/7)) (Corollary A.1 ). The author is not aware of any previous work on transfer operators for strong powers of circulant graphs, but the approach is classical, and closely related to the use of transfer matrices in statistical physics and combinatorics, as well as the use of group actions to decompose state spaces in dynamical systems and representation theory. The author is in the process of collecting the numerical data and code for computational replication. 2. Transfer formulation Let n\geq 3 and let C\subset\mathbb{Z}_{n}\setminus\{0\} satisfy C=-C . Define the circulant graph G=\Cay(\mathbb{Z}_{n},C), with edge set \{(i,j):j-i\in C\} . Let B:=C\cup\{0\} denote the closed connection set (the closed neighborhood of the identity in the Cayley graph). We write \mathcal{I}(G) for the family of independent sets of G . For d\geq 1 , the d -th strong power G^{\boxtimes d} has vertex set \mathbb{Z}_{n}^{d} with adjacency u\sim v\iff u\neq v\text{ and }v_{j}-u_{j}\in B\text{ for all }j. We define the Minkowski difference I-J=\{a-b\bmod n:a\in I,\,b\in J\} for subsets I,J\subseteq\mathbb{Z}_{n} . Proposition 2.1 . A sequence (S_{1},\dots,S_{d}) with S_{i}\subseteq\mathbb{Z}_{n} corresponds to an independent set of G^{\boxtimes d} if and only if: (1) S_{i}\in\mathcal{I}(G) for each i , and (2) (S_{i}-S_{i+1})\cap B=\varnothing for each i . Proof. Immediate from the coordinate-wise definition of strong-product adjacency. ∎ Remark 2.2 (Geometric interpretation) . The transfer formulation describes independent sets on strong cylinders G\boxtimes P_{d} (free boundary conditions) and strong tori G\boxtimes C_{d} (periodic boundary conditions). These correspond to one-dimensional sequences of cross-sections of the full strong product G^{\boxtimes d} . 2.1. The transfer operator Definition 2.3 . The transfer matrix T:\mathbb{R}^{\mathcal{I}(G)}\to\mathbb{R}^{\mathcal{I}(G)} is defined by T[I,J]=\begin{cases}1,&(I-J)\cap B=\varnothing,\\ 0,&\text{otherwise.}\end{cases} Equivalently, defining c:\mathbb{Z}_{n}\to\{0,1\} by c(j)=\mathbf{1}[j\notin B] , T[I,J]=\prod_{u\in I}\prod_{v\in J}c(u-v). The product form is the one that connects to the Fourier analysis in Section 3 . Definition 2.4 . The fugacity-weighted transfer matrix is M(x)=T\cdot D_{x},\qquad D_{x}=\diag(x^{|J|})_{J\in\mathcal{I}(G)}. Proposition 2.5 (Transfer formula) . For free boundary conditions, I(G^{\boxtimes d},x)=\mathbf{1}^{T}M(x)^{d-1}\mathbf{w}, where \mathbf{w}(J)=x^{|J|} . For periodic boundary conditions, I(G^{\boxtimes d},x)=\tr(M(x)^{d}). Proof. Standard transfer-matrix expansion: each compatible sequence of d layer-states contributes \prod_{i}x^{|S_{i}|} to the generating function. ∎ Remark 2.6 (Trace formula) . The periodic trace formula \tr(M(x)^{d}) correctly computes independence polynomials for d\geq 2 . The case d=1 corresponds to a degenerate one-layer torus, the standard C_{n} graph,and is handled separately. 3. Fourier structure of the compatibility kernel The discrete Fourier transform of the constraint function c over \mathbb{Z}_{n} provides the bridge between the adjacency spectrum and the transfer spectrum. Let \omega=e^{2\pi i/n} and \mu_{k}=1+2\cos(2\pi k/n) be the eigenvalues of the cycle C_{n} . Proposition 3.1 . For the strong product kernel B=\{-1,0,1\} , \widehat{c}(0)=n-3,\qquad\widehat{c}(k)=-\mu_{k}\quad(k\neq 0), where \widehat{c}(k)=\sum_{j=0}^{n-1}c(j)\,\omega^{-jk} . Proof. We have \widehat{c}(k)=n\delta_{k,0}-\sum_{j\in B}\omega^{-jk} . For k\neq 0 , \sum_{j\in B}\omega^{-jk}=1+\omega^{k}+\omega^{-k}=1+2\cos(2\pi k/n)=\mu_{k} . ∎ Thus the Fourier eigenvalues of the constraint function are the negatives of the adjacency eigenvalues. The \mathrm{Dih}(n) block decomposition (Section 4 ) separates the k=0 mode (also known as "the DC component") \widehat{c}(0)=n-|B|\in\mathbb{Q} , that controls the combinatorial sector, from the k\neq 0 modes (also known as "the AC component") \widehat{c}(k)=-\mu_{k}\in K , that control the cyclotomic sector, where K=\mathbb{Q}(\cos(2\pi/n)) is the maximal real subfield of the n -th cyclotomic field. Lemma 3.2 (Fourier realization of isotypic blocks) . The action of the transfer operator on each isotypic component is determined by the Fourier coefficients \widehat{c}(k) . In particular, the trivial component depends only on \widehat{c}(0) , while the \rho_{k} components depend on \widehat{c}(k) and \widehat{c}(-k) . Sketch. The transfer operator is defined by convolution of the function c(u-v) . Passing to the group algebra \mathbb{C}[\mathbb{Z}_{n}] , convolution diagonalizes under the discrete Fourier transform. The dihedral action organizes these Fourier modes into isotypic components. ∎ Thus, the compatibility kernel is the complement of the closed neighborhood operator, and its Fourier spectrum is the negation of the adjacency spectrum. 4. Equivariance and block decomposition The dihedral group \mathrm{Dih}(n)=D_{2n} acts on \mathbb{Z}_{n} by rotations and reflections, hence on \mathcal{I}(G) . Proposition 4.1 . The operators T and M(x) commute with the action of \mathrm{Dih}(n) . Proof. Both the independence condition and the compatibility condition (I-J)\cap B=\varnothing are invariant under rotations and reflections of \mathbb{Z}_{n} . The weight |I| is also invariant, so D_{x} commutes with the action. ∎ Since \mathrm{Dih}(n) acts on the finite set \mathcal{I}(G) , the permutation representation \mathbb{C}[\mathcal{I}(G)] decomposes into isotypic components. For odd prime n , \mathrm{Dih}(n) has two one-dimensional irreducible representations ( \chi_{0} trivial, \chi_{1} sign) and (n-1)/2 two-dimensional representations \rho_{k} , k=1,\ldots,(n-1)/2 . Theorem 4.2 (Block decomposition) . There exists a \mathrm{Dih}(n) -equivariant change of basis \mathcal{F} such that \mathcal{F}T\mathcal{F}^{-1}=\bigoplus_{\rho\in\widehat{\mathrm{Dih}(n)}}\left(T_{\rho}\otimes I_{\dim\rho}\right),\qquad T_{\rho}\in\End(\mathbb{C}^{m_{\rho}}), and hence \chi_{T}(\lambda)=\prod_{\rho}\chi_{T_{\rho}}(\lambda)^{\dim\rho}. Proof. By Proposition 4.1 , T lies in \End_{\mathrm{Dih}(n)}(\mathbb{C}[\mathcal{I}(G)]) . By Schur’s lemma, on each isotypic summand \mathbb{C}^{m_{\rho}}\otimes