Golden Ratio Growth and Phase Transitions in Chromatic Counts of Circular Chord Graphs
Rogelio N. Lopez-Bonilla, Julian Allagan, Shawn M. Langley, Angel J. Clinton · 2025
Read Golden Ratio Growth and Phase Transitions in Chromatic Counts of Circular Chord Graphs by Rogelio N. Lopez-Bonilla, Julian Allagan, Shawn M. Langley, Angel J. Clinton (2025) 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-2509-05845.txt.
Introduction
Counting the proper colorings of circular chord graphs is the task of a 2025 paper by Rogelio N. Lopez-Bonilla and three co-authors. These graphs start from a ring of points and add chords of fixed offset, plus diameters when the ring is even. The count of three-colorings turns out to follow striking patterns.
Using transfer matrices, tables that carry counts step by step around the ring, the authors derive exact formulas for the chord length three case. Along odd rings the counts grow at the golden ratio rate, tied to the Lucas number sequence, with extra periodic terms. Even rings need a paired-window matrix that respects the diameters. The counts show strong modular patterns, and the methods double as feasibility checks for cyclic scheduling problems such as airline gate assignment.
Catalog record
| CREATOR | Rogelio N. Lopez-Bonilla, Julian Allagan, Shawn M. Langley, Angel J. Clinton |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-05845
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Golden Ratio Growth and Phase Transitions in Chromatic Counts of Circular Chord Graphs Rogelio N. Lopez-Bonilla, Julian Allagan, Shawn M. Langley, Angel J. Clinton Abstract . We study generalized circular chord graphs 𝒞 n ( k ) \mathcal{C}^{(k)}_{n} , formed from a cycle C n C_{n} by adding fixed-offset chords of length k k and, for even n n , diameters. Using transfer matrix methods, we derive exact formulas for 3-colorings when k = 3 k=3 : for odd n n , we obtain P ( 𝒞 n ( 3 ) , 3 ) = L n + 2 cos ( 2 π n 3 ) + 2 s n + 2 P(\mathcal{C}_{n}^{(3)},3)=L_{n}+2\cos\left(\frac{2\pi n}{3}\right)+2s_{n}+2 where L n L_{n} is the Lucas sequence and ( s n ) (s_{n}) satisfies s n + 3 = − s n + 2 − s n s_{n+3}=-s_{n+2}-s_{n} , yielding golden-ratio asymptotic growth φ n + O ( ρ n ) \varphi^{n}+O(\rho^{n}) along odd indices. For even n n , we construct a paired-window transfer matrix that exactly enumerates P ( 𝒞 2 m ( 3 ) , 3 ) P(\mathcal{C}_{2m}^{(3)},3) while capturing diameter constraints. The chromatic counts exhibit pronounced modular patterns across residue classes without universal vanishing rules (see OEIS A383733). We provide efficient algorithms for exact enumeration and demonstrate applications to cyclic scheduling problems where these results serve as feasibility engines for airline gate assignment, wireless sensor networks, and multiprocessor task coordination. 1. Introduction Graph coloring traces its origins to the four-color problem and connects combinatorics with algebraic methods through the chromatic polynomial P(G,x) , which counts proper x -colorings of graph G [ 3 , 18 ] . Classical families exhibit well-understood behavior: cycles satisfy P(C_{n},x)=(x-1)^{n}+(-1)^{n}(x-1) and show parity-driven oscillations [ 22 ] . By contrast, circulant and circulant-like graphs with edges at fixed modular offsets remain comparatively underexplored from the viewpoint of exact chromatic polynomials [ 2 ] . This paper studies a natural circulant-type family we call generalized circular chord graphs, denoted \mathcal{C}^{(k)}_{n} : starting from the cycle C_{n} , we add fixed-offset chords of length k , and for even n we also add diameter edges. The resulting graphs are vertex-transitive and interpolate between sparse cycles and denser circulant structures. For k=3 and q=3 colors we observe chromatic phase transitions manifesting as modular patterns in P(\mathcal{C}^{(3)}_{n},3) across residue classes of n . These transitions are driven by the interplay of cycle edges, k -chords, and diameter constraints, creating distinct structural regimes where the chromatic feasibility changes systematically with n .” Methodologically, we combine optimized backtracking with transfer-matrix constructions. Our main theoretical contributions for k=3 , q=3 are: (i) for odd n we derive an exact spectral decomposition yielding a precise order-7 linear recurrence and asymptotic law P(\mathcal{C}^{(3)}_{n},3)=\varphi^{n}+O(\rho^{n}) with dominant base \varphi=(1+\sqrt{5})/2 ; (ii) for even n we construct a paired-window transfer matrix that exactly enumerates P(\mathcal{C}^{(3)}_{2m},3) and captures residue-class effects; (iii) for general (k,q) we show that P(\mathcal{C}^{(k)}_{n},q)=\mathrm{tr}(A_{k,q}^{n}) for a finite matrix A_{k,q} , establishing that n\mapsto P(\mathcal{C}^{(k)}_{n},q) satisfies a linear homogeneous recurrence. We report exact counts through n=35 for k=3 and visualize the modular structure by residue class. Several multiples of 4 are nonzero, underscoring that no blanket vanishing rule applies across all residues. We also include applied examples demonstrating how the transfer-matrix machinery serves as a fast feasibility engine for cyclic scheduling problems. Definition 1.1 . For n\geq 3 and k\in\mathbb{N} with 1<k<n/2 , the generalized circular chord graph \mathcal{C}_{n}^{(k)}=(V,E) has vertex set V=\mathbb{Z}_{n} and edges: (i) Cycle edges: (i,i+1\bmod n) , forming the base cycle C_{n} . (ii) Chord edges: (i,i+k\bmod n) , adding chords of fixed offset k . (iii) Diameter edges: For even n , (i,i+n/2\bmod n) , connecting diametrically opposite vertices. This construction ensures vertex-transitivity and variable edge density, making \mathcal{C}_{n}^{(k)} ideal for studying chromatic properties across structural regimes. The interplay of cycles, chords, and diameters creates a rich combinatorial landscape distinct from classical graph families. 2. Computational Methodology We developed an optimized backtracking algorithm with memoization to count valid 3-colorings efficiently, reducing complexity from \mathcal{O}(3^{n}\cdot m) in brute-force enumeration to \mathcal{O}(2.8^{n}) , where m is the number of edges. The complete algorithm is presented in Algorithm 1 . Algorithm 1 Optimized 3-Coloring Counter 1: Initialize color array c[0..n-1] to -1 2: Memoize partial colorings in hash table 3: function CountColorings (v) 4: if v=n then return 1 5: end if 6: if memoized( c[0..v] ) then return memoized value 7: end if 8: \text{total}\leftarrow 0 9: for color \in\{0,1,2\} do 10: if color \neq c[v-1] , c[(v-k)\bmod n] , c[(v-n/2)\bmod n] (if applicable) then 11: c[v]\leftarrow\text{color} 12: \text{total}\leftarrow\text{total}+\text{CountColorings}(v+1) 13: end if 14: end for 15: Memoize partial result return total 16: end function We also employed a greedy coloring algorithm with the largest-first heuristic to estimate \chi(\mathcal{C}_{n}^{(k)}) , providing tight upper bounds with typically \chi(\mathcal{C}_{n}^{(k)})\in\{3,4\} . These computational tools enabled detailed empirical analysis of P(\mathcal{C}_{n}^{(k)},3) , revealing the modular patterns central to our findings. 3. Transfer Matrix Framework and Main Results The fundamental observation underlying our approach is that for fixed (k,q) , the chromatic counts P(\mathcal{C}^{(k)}_{n},q) can be expressed as traces of powers of a finite transfer matrix. Theorem 3.1 . For fixed parameters (k,q) , there exists a finite matrix A_{k,q} such that P(\mathcal{C}^{(k)}_{n},q)=\mathrm{tr}(A_{k,q}^{n}) . Consequently, the sequence n\mapsto P(\mathcal{C}^{(k)}_{n},q) satisfies a linear homogeneous recurrence with constant coefficients. Proof. We use a window automaton of length k : a state is a legal k -tuple (c_{i},\ldots,c_{i+k-1})\in\{0,\ldots,q-1\}^{k} with c_{j+1}\neq c_{j} for all j . A transition (c_{i},\ldots,c_{i+k-1})\to(c_{i+1},\ldots,c_{i+k}) is allowed if and only if c_{i+k}\notin\{c_{i+k-1},c_{i}\} . This yields a finite directed graph with adjacency matrix A_{k,q} . On a cycle, q -colorings correspond to closed walks of length n , hence P(\mathcal{C}^{(k)}_{n},q)=\mathrm{tr}(A_{k,q}^{n}) . Since A_{k,q} is fixed, the power-sum sequence \mathrm{tr}(A_{k,q}^{n}) is a finite \mathbb{C} -linear combination of \lambda^{n} over the distinct eigenvalues \lambda of A_{k,q} , establishing the linear recurrence property. ∎ Remark 3.1 . For q=3 and general k , the window has at most 3\cdot 2^{k-1} states since adjacent entries must differ, and color-rotation symmetry often reduces the effective order substantially. Before presenting the main results for k=3 , we establish the foundational theorems upon which our analysis depends. Theorem 3.2 (Cayley-Hamilton theorem) . Let A be an n\times n matrix over any commutative ring, and let \chi_{A}(\lambda)=\det(\lambda I-A) be its characteristic polynomial. Then \chi_{A}(A)=0 . Theorem 3.3 (Skolem-Mahler-Lech theorem) . Let (u_{n})_{n\geq 0} be a linear recurrence sequence over a field of characteristic zero. Then the zero set Z=\{n\geq 0:u_{n}=0\} is the union of a finite set and finitely many arithmetic progressions. The Skolem-Mahler-Lech theorem follows from the foundational work of Skolem (1934) [ 20 ] , Mahler (1935) [ 15 ] , and Lech (1953) [ 14 ] , with modern expositions available in Everest et al. [ 9 ] . For the specific case k=3 and q=3 , we obtain detailed results depending on the parity of n . For odd n (no diameter edges), the transfer matrix block-diagonalizes under color-rotation symmetry. The characteristic polynomial factors as \chi_{A}(\lambda)=(\lambda^{2}-\lambda-1)(\lambda^{2}+\lambda+1)(\lambda^{3}+\lambda^{2}+1)^{2}, yielding seven distinct eigenvalues with some occurring at higher algebraic multiplicities due to the squared cubic factor. This spectral