🔬 condensed matter

Chromatic Zeros on the Limit $G^{(p,\ell)}_\infty$ of the Family $G^{(p,\ell)}_m$ of Hierarchical Graphs

This paper calculates the continuous accumulation set of chromatic polynomial zeros for an infinite family of hierarchical graphs by employing real-space renormalization group transformations on the Potts model partition function to determine critical points and ground-state degeneracies for various structural parameters.

Original authors: Shu-Chiuan Chang, Robert Shrock

Published 2026-07-09

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Shu-Chiuan Chang, Robert Shrock

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, magical coloring book. But this isn't just any book; it's a book where the pages are made of infinite, self-repeating patterns called hierarchical graphs. Think of these like a fractal snowflake or a never-ending set of Russian nesting dolls. You start with a simple shape, and then you take every single line (or "edge") in that shape and replace it with a whole new, slightly more complex set of lines. You do this over and over again, forever.

The authors of this paper, Shu-Chiuana Chang and Robert Shrock, are playing a game with these infinite shapes. The game is called chromatic coloring. The rule is simple: you have a certain number of colors (let's call this number $q$ ), and you must color every dot (vertex) on the graph so that no two dots touching each other have the same color.

The big question they are asking is: What happens if you keep adding more and more colors? Or, more specifically, at what exact number of colors does the game suddenly break down?

The Magic Line of Chaos

In the world of math, when you have a finite graph, you can count exactly how many ways you can color it. But when you zoom out to the "infinite limit" (where the graph gets infinitely big), the answers stop being single numbers and start behaving like a wild, swirling cloud of possibilities.

The authors discovered a specific "magic line" in the complex number plane (a map that includes both real numbers and imaginary numbers) called $B_q$ . This line acts like a storm front or a phase boundary.

On one side of the line, the coloring game behaves in one predictable way.
On the other side, it behaves in a completely different way.
Right on the line, the game is in a state of chaotic transition. This is where the "zeros" of the coloring polynomial live.

The paper calculates exactly where this storm front lands for different types of fractal graphs, defined by two numbers: $p$ (how many paths you split an edge into) and $\ell$ (how long those paths are).

The "Rightmost" and "Leftmost" Danger Zones

The authors mapped out these storm fronts for many different combinations of $p$ and $\ell$ . They found some very specific, interesting points where the storm front crosses the "real" number line (the line of normal, everyday numbers).

The Rightmost Point ( $q_c$ ): This is the highest number of colors you can have before the graph's behavior changes drastically.
- For the simplest case, where $p=2$ and $\ell=2$ (a diamond-shaped fractal), this magic number is exactly 3.
- If you make the paths longer (increasing $\ell$ ), this number drops. For example, if you keep $p=2$ but make the paths 4 units long, the magic number drops to about 2.145883.
- If you add more paths (increasing $p$ ), the number shoots up. For $p=8$ and $\ell=2$ , the number jumps to 11.607116.
- The authors observed that as the paths get infinitely long, this number seems to settle down and approach 2, no matter how many paths you have.
The Leftmost Point ( $q_L$ ): This is the lowest number where the storm front touches the line.
- In many cases, this point is 0.
- However, the authors found something surprising: if you have more paths than the length of the paths ( $p > \ell$ ), the storm front actually crosses into negative numbers.
- For example, with $p=8$ and $\ell=2$ , the leftmost point is -2.136550. This is a big deal because, in standard graph theory, coloring numbers are usually positive. The authors suggest that for these specific fractal shapes, an infinite set of "impossible" coloring numbers (negative ones) gets closer and closer to the negative side of the number line, even though you can't actually color a graph with a negative number of colors in the real world.

The "Bubble" and "Dust" Patterns

When the authors looked at the storm front for cases where both $p$ and $\ell$ are even numbers (like $p=2, \ell=4$ ), they found a fascinating structure.

Instead of a single line, the storm front creates an infinite sequence of bubbles along the real number line.
Imagine a row of bubbles getting smaller and smaller as you move to the left. Inside each bubble, the coloring behavior flips back and forth between two different states (like white and blue regions on their maps).
These bubbles get infinitely small as they approach a limit point called $q_\infty$ . For the $p=2, \ell=2$ case, this limit is 32/27 (about 1.185185).
The paper notes that while they can see the first few bubbles clearly, the infinite nature of the sequence means there are infinitely many of them, shrinking down to a point.

For cases where $p$ is odd and $\ell$ is even, the pattern is simpler: there is just one crossing point in the middle, like a single island in a sea of color.

For cases where both $p$ and $\ell$ are odd, the storm front looks like a cusp (a sharp, pointed wedge) that opens up. In some cases, these wedges get so thin they seem to touch the real number line at a specific point called $q_x$ . For $p=3, \ell=3$ , this point is 27/16 (exactly 1.6875).

What They Didn't Find (and What They Ruled Out)

The authors are very careful about what they claim.

They do not claim that the graph has a "solution" or that the problem is "solved" in a general sense. They have calculated specific points for specific fractal families.
They do not say that the storm front is always connected. In fact, for some cases (like $p=2, \ell=6$ ), they see "dust-like" structures that suggest the storm front might be broken into many tiny, disconnected pieces. They explicitly state that they are not sure if the front is connected or not for all cases and that this needs more study.
They rule out the idea that the leftmost point is always positive. They explicitly found cases where it is negative, which contradicts the behavior of many other known graphs.
They do not claim that the negative numbers are "real" colorings. They clarify that while the mathematical zeros approach these negative numbers, the actual physical act of coloring a graph with a negative number of colors doesn't make sense. The negative crossing is a mathematical feature of the infinite limit, not a physical reality.

The Bottom Line

This paper is a detailed map of the "weather patterns" for an infinite family of fractal coloring games. By using a clever mathematical trick (renormalization group transformation), the authors were able to predict exactly where the chaos happens for different shapes.

They found that:

The "tipping point" for colors ( $q_c$ ) depends heavily on the shape of the fractal.
For some shapes, the chaos spills over into negative numbers, a phenomenon never seen before in non-random graphs.
The patterns of chaos can be simple (one crossing) or incredibly complex (infinite bubbles and dust-like clouds).

The authors present these results as calculated values and observed patterns from their simulations and mathematical derivations. They suggest that as the fractal paths get longer, the tipping point for colors seems to settle near 2, but they leave the door open for further investigation into the connectivity of these chaotic regions. It's a vivid, playful, and rigorous look at how infinite complexity emerges from simple, repeating rules.

Technical Summary: Chromatic Zeros on the Limit $G(p,\ell)_\infty$ of the Family $G(p,\ell)_m$ of Hierarchical Graphs

Problem Statement
The paper investigates the continuous accumulation set of zeros, denoted $B_q$ , of the chromatic polynomial $P(G, q)$ for a specific family of hierarchical graphs, $G(p,\ell)_m$ , in the limit as the iteration index $m \to \infty$ . The chromatic polynomial counts the number of proper $q$ -colorings of a graph's vertices. In statistical mechanics, this polynomial corresponds to the zero-temperature partition function of the $q$ -state Potts antiferromagnet. While the behavior of chromatic zeros is well-studied for regular lattices and specific fractal families (such as the Diamond Hierarchical Lattice, $D_m \equiv G(2,2)_m$ ), this work extends the analysis to the broader family $G(p,\ell)_m$ , defined by parameters $p$ (the number of parallel paths) and $\ell$ (the length of each path in edges), where $p \ge 2$ and $\ell \ge 2$ . The primary objective is to map the locus $B_q(p, \ell)$ in the complex $q$ -plane and determine specific points where this locus intersects the real axis, including the maximal crossing point $q_c$ , the leftmost crossing point $q_L$ , and various interior crossing points.

Methodology
The authors employ an exact real-space renormalization group (RG) approach, leveraging the relationship between the chromatic polynomial and the Potts model partition function $Z(G, q, v)$ evaluated at the Boltzmann variable $v = -1$ .

RG Transformation: The partition function of the hierarchical graph $G(p,\ell)_{m+1}$ is related to that of $G(p,\ell)_m$ via an exact, closed-form transformation. Specifically, $Z(G(p,\ell)_{m+1}, q, v) = Z(G(p,\ell)_m, q, v') [A_\ell(q, v)]^{p(p\ell)^m}$ , where the new variable $v'$ is a rational function of the previous $v$ and $q$ :
$v' = F_{(p,\ell),q}(v) = \left[ \frac{(q+v)^\ell + (q-1)v^\ell}{(q+v)^\ell - v^\ell} \right]^p - 1$
Iterative Dynamics: The locus $B_q(p, \ell)$ is identified as the boundary in the complex $q$ -plane that separates regions of distinct asymptotic behavior of the $m$ -fold iterated RG transformation $F^m_{(p,\ell),q}(v)$ as $m \to \infty$ , starting from the initial condition $v_0 = -1$ .
Numerical and Analytical Calculation:
- Region Diagrams: The authors numerically iterate the RG map for various complex values of $q$ $q$ . Points are classified into three regions based on the limit behavior:
  - White: $v_\infty = 0$ (corresponding to $y_\infty = 1$ ).
  - Blue: $v_\infty = \infty$ (corresponding to $y_\infty = \infty$ ).
  - Black: $v_\infty$ is finite and non-zero (corresponding to $y_\infty \neq 1, \infty$ ).
- Analytical Solutions: For specific crossing points on the real axis, the authors derive polynomial equations by setting the RG fixed-point condition $F(v) = v$ or analyzing the stability of the iteration. They solve these equations to find exact or high-precision numerical values for $q_c$ , $q_L$ , $q_\infty$ , and $q_{int}$ .

Key Contributions and Results

Generalization of Hierarchical Graphs: The study generalizes previous work on the Diamond Hierarchical Lattice ( $p=2, \ell=2$ ) to arbitrary integers $p, \ell \ge 2$ . The authors calculate the effective vertex degree and Hausdorff dimension for these fractal limits.
Classification of Loci by Parity: The structure of the chromatic locus $B_q(p, \ell)$ $B_{q} (p, ℓ)$ depends critically on the parity of $p$ $p$ and $\ell$ $ℓ$ . The paper categorizes the results into four classes:
- $p$ even, $\ell$ even: The locus exhibits an infinite sequence of crossing points $q_r$ on the real axis within the interval $(q_\infty, q_c)$ , converging to a limit point $q_\infty$ from above. The region diagram shows alternating "bubble" regions of white and blue phases separated by these crossing points, terminating in a black region at $q_\infty$ .
- $p$ odd, $\ell$ even: The locus crosses the real axis at a single interior point $q_{int}$ between $q_L$ and $q_c$ . The region diagram consists of a white exterior, a blue region between $q_c$ and $q_{int}$ , and a black region between $q_{int}$ and $q_L$ .
- $p$ odd, $\ell$ odd: The locus features a horizontally oriented cusp at $q_c$ and complex-conjugate vertical cusp-like structures extending inward to touch the real axis at a point $q_x$ . The entire interior interval $(q_L, q_c)$ is black.
- $p$ even, $\ell$ odd: Similar to the odd-odd case, the locus has a cusp at $q_c$ . Notably, for cases like $(2,5)$ and $(2,7)$ , the locus contains Mandelbrot-like sub-structures.
Discovery of Negative Real-Axis Crossings: A significant finding is that for cases where $p > \ell$ , the leftmost crossing point $q_L$ becomes negative. This is the first known instance of a continuous accumulation set of chromatic zeros for a non-random family of graphs crossing the negative real $q$ -axis. While graph theory dictates that $P(G, q)$ has no zeros on the negative real axis for finite graphs, the accumulation set $B_q$ can approach arbitrarily close to negative values in the thermodynamic limit.
Specific Calculations: The authors provide explicit values for:
- $q_c(p, \ell)$ : The maximal crossing point, which is monotonically increasing with $p$ and decreasing with $\ell$ .
- $q_L(p, \ell)$ : The leftmost crossing point, which is $0$ if $p \le \ell$ and negative if $p > \ell$ .
- $q_\infty(p, \ell)$ : The limit of the infinite sequence for even-even cases, which is symmetric under the exchange of $p$ and $\ell$ .
- $q_{int}(p, \ell)$ and $q_x(p, \ell)$ : Interior crossing points for specific parity classes.
Ground-State Degeneracy: The paper calculates the ground-state degeneracy per vertex, $W(G(p,\ell)_\infty, q)$ , at the point $q_c$ , observing interesting features in the entropy behavior.

Significance and Claims
The authors state that this work extends the understanding of chromatic zeros from the specific case of the Diamond Hierarchical Lattice to a broader family of hierarchical graphs. By utilizing exact RG transformations, they provide a rigorous method to determine the continuous accumulation sets of zeros without relying on the asymptotic analysis of dominant eigenvalues (which is typical for strip graphs).

The paper claims the discovery of the first non-random graph families where the chromatic zero locus $B_q$ crosses the negative real axis, challenging the intuition derived from finite graph properties. Furthermore, the identification of Mandelbrot-like structures and the detailed classification of region diagrams based on the parity of $p$ and $\ell$ offer new insights into the complex dynamics of RG transformations in statistical mechanical models on fractal lattices. The results serve as a comprehensive reference for the behavior of the Potts antiferromagnet on these hierarchical structures, particularly regarding the ground-state entropy and the distribution of chromatic zeros.

The Magic Line of Chaos

The "Rightmost" and "Leftmost" Danger Zones

The "Bubble" and "Dust" Patterns

What They Didn't Find (and What They Ruled Out)

The Bottom Line

More like this