6
$\begingroup$

Question: What is the largest Beraha number known to be an accumulation point of real zeros of the chromatic polynomial of planar graphs?

Background: The Beraha numbers $B_n=2+2cos(2\pi/n), n=2,3,\ldots$ are well known in the study of the chromatic polynomial of planar triangulations, and more generally of planar graphs. Early results in the subject are due to W.T. Tutte: "On chromatic polynomials and the golden ratio" (J. Combinatorial Theory 9 (1970) 289–296) gave a bound on the value of the chromatic polynomial at $B_5={\phi}+1$, where $\phi$ is the golden ratio; "More about chromatic polynomials and the golden ratio" (1970 Combinatorial Structures and their Applications, 439–453) established the famous Tutte's golden identity.

My question concerns the observation of S. Beraha ("Infinite non-trivial families of maps and chromials", Thesis, Johns Hopkins University, 1975) that zeros of the chromatic polynomial of large planar graphs seem to accumulate to the numbers $B_n$. (The special role played by the Beraha numbers was also illustrated in the paper http://arxiv.org/abs/0711.0016 which gave a local relation satisfied by the chromatic polynomial of planar graphs at each $B_n$.)

There are different ways to interpret Beraha's conjecture; my question concerns accumulation points of real zeros. In "Limits of chromatic zeros of some families of maps" (J. Combin. Theory Ser. B 28 (1980), 52–65) S. Beraha, J. Kahane and N.J. Weiss gave examples of (periodic) graphs where $B_5$ and $B_7$ are accumulation points.

I am wondering whether there are higher Beraha numbers that are also known to be accumulation points of real zeros. A more precise question concerns periodic graphs, like the ones considered by Beraha-Kahane-Weiss. Is there a conjecture one way or another?

[It is known (G.F. Royle, "Planar triangulations with real chromatic roots arbitrarily close to four", Ann. Comb. 12 (2008), 195–210) that there are graphs for which real zeros accumulate to 4, although I believe these examples are not "periodic". Also, the chromatic polynomial has been studied for various families of planar graphs in the context of statistical mechanics; I do not know whether this exhibited $B_n$, $n>7$ as accumulation points.]

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

I don't think that there are known families of graphs with (real) chromatic roots converging to particular Beraha numbers.

Alan Sokal and Jesus Salas wrote a series of papers, the first of which is titled "Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models I. General Theory and Square-Lattice Chromatic Polynomial" (http://arxiv.org/abs/cond-mat/0004330) where they claim evidence that certain families have roots converging to $B_2$, $B_3$, $\ldots$, $B_5$.

One intriguing leftover from their paper is that they can show that despite the likelihood that they are accumulation points of roots, no Beraha numbers are actually chromatic roots themselves - except possibly $B_{10}$. (I've looked quite hard to find a chromatic polynomial with $B_{10}$ as a root, but with no luck.)

The graphs that I used in the paper of mine that you quoted were actually just modifications of the original family of graphs used by Beraha-Kahane in their famous paper "Is the four-color conjecture almost false?" So while I am not sure what you mean by periodic, I'm pretty sure that if the graphs they used are periodic, then so are the graphs that I used.

(One problem is that statistical physicists working with strips of lattices have to make some decision about the "edges" of their lattice; if they "wrap-round" so that the left-hand edge is identified with the right-hand edge, then they call that "periodic boundary conditions." But I don't think that that is the meaning you had in mind?)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the answer; Beraha-Kahane-Weiss considered families of examples built by stacking identical layers (4-rings,5-rings,..), that's what I referred to as "periodic". (The actual graph whose chromatic polynomial is being computed is the planar dual.) The graphs in your paper with real roots limiting to 4 are of this type, but also "capped off" by interesting graphs at the two ends. It seems to me that the answer to the question "what points are limits of real zeros?" may be different, depending on whether one allows arbitrary planar graphs or just large pieces of regular planar lattices. $\endgroup$
    – Slava Krushkal
    Feb 7, 2015 at 13:34
  • $\begingroup$ The lattices usually considered by the statistical physicists have this property of stacking layers. This is nice because then "adding a layer" is reflected in the chromatic polynomial as multiplying by a matrix - the matrix they call the "transfer matrix". Then adding lots of layers (i.e. one dimension tending towards infinity) means multiplying by higher and higher powers of the matrix. But the behaviour of high powers of a matrix are determined by its eigenvalues. $\endgroup$
    – Gordon Royle
    Feb 7, 2015 at 14:17
1
$\begingroup$

It has recently been shown by Harvey and Royle (https://research-repository.uwa.edu.au/en/publications/chromatic-roots-at-2-and-the-beraha-number-bsub10sub) that $B_{10}$ is the largest Beraha number that appears as a root of a chromatic polynomial. $B_{10}$ is the largest Beraha number whose minimal polynomial has no roots in the forbidden intervals. Harvey and Royle found a couple examples of graphs with chromatic polynomials that have $B_10$ as a root. I am not sure if larger ones can appear as accumulation points however.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.