The Structure of Chromatic Polynomials of Planar Triangulation Graphs and Implications for Chromatic Zeros and Asymptotic Limiting Quantities Robert Shrock and Yan Xu C. N. Yang Institute for Theoretical Physics 2 Stony Brook University 1 0 Stony Brook, N. Y. 11794 2 n We present an analysis of the structure and properties of chromatic polynomials a J P(G ,q) of one-parameter and multi-parameter families of planar triangulation 0 pt,m(cid:126) 2 graphsG , wherem(cid:126) = (m ,...,m )isavectorofintegerparameters. Weusethese pt,m(cid:126) 1 p ] h to study the ratio of |P(G ,τ +1)| to the Tutte upper bound (τ −1)n−5, where pt,m(cid:126) p √ - τ = (1+ 5 )/2 and n is the number of vertices in G . In particular, we calculate h pt,m(cid:126) t a limiting values of this ratio as n → ∞ for various families of planar triangulations. m [ We also use our calculations to study zeros of these chromatic polynomials. We 1 study a large class of families G with p = 1 and p = 2 and show that these have v pt,m(cid:126) 0 a structure of the form P(G ,q) = c λm+c λm+c λm for p = 1, where 0 pt,m Gpt,1 1 Gpt,2 2 Gpt,3 3 2 4 λ1 = q−2, λ2 = q−3, and λ3 = −1, and P(Gpt,m(cid:126),q) = (cid:80)3i1=1(cid:80)3i2=1cGpt,i1i2λmi11λmi22 . 1 for p = 2. We derive properties of the coefficients c and show that P(G ,q) 20 Gpt√,(cid:126)i pt,m(cid:126) has a real chromatic zero that approaches (1/2)(3 + 5 ) as one or more of the 1 : v m → ∞. The generalization to p ≥ 3 is given. Further, we present a one-parameter i i X familyofplanartriangulationswithrealzerosthatapproach3frombelowasm → ∞. r a Implicationsfortheground-stateentropyofthePottsantiferromagnetarediscussed. I. INTRODUCTION In this paper we present exact results on the structure and properties of chromatic poly- nomials P(G ,q) of one-parameter and multi-parameter families of planar triangulation pt,m(cid:126) (pt) graphs G , where m(cid:126) = (m ,...,m ) is a vector of integer parameters. Our results pt,m(cid:126) 1 p substantially generalize our previous study in [1]. In standard notation we let G = (V,E) be a graph with vertex and edge sets V and E, and denote the number of vertices and edges as n = n(G) = |V| and e(G) = |E|, respectively. The resultant set of faces is denoted F(G), with cardinality f(G) = |F(G)|. We recall the definitions of a planar graph G as one that can be drawn in a plane without any crossing edges, and a triangulation as a graph all of whose faces are triangles. For an arbitrary graph G, the chromatic polynomial P(G,q) enumerates the number of ways of associating q colors with the vertices of G, subject to the constraint that adjacent vertices have different colors (called a proper q-coloring of G) [2]. The minimum number of colors for a proper q-coloring of a graph G is the chromatic number of G, denoted χ(G). Without loss of generality, we restrict here to graphs G that are connected, have no multiple edges, and have no loops (where a loop is defined as an edge that connects a vertex back to itself). Multiple edges are also excluded by our restriction here to triangulation graphs, since they produce faces that are not triangles. An important identity is P(G,q) = Z (G,q,0), where Z (G,q,T) denotes the partition function of PAF PAF the Potts antiferromagnet (PAF) on the graph G at temperature T. Because of this identity, properties of chromatic polynomials are of interest both for mathematical graph theory and for statistical physics. A particularly significant feature of the Potts antiferromagnet is the fact that it generically exhibits nonzero ground-state (i.e., zero-temperature) entropy per vertex for sufficiently large q on a given graph. The chromatic polynomial of a graph G may be computed via the deletion-contraction relation P(G,q) = P(G−e,q)−P(G/e,q), where G−e denotes G with an edge e deleted and G/e denotes the graph obtained by deleting e and identifying the vertices that it connected. From this follows the cluster formula P(G,q) = (cid:80) (−1)e(G(cid:48)) qk(G(cid:48)), where G(cid:48) = (V,E(cid:48)) G(cid:48)⊆G withE(cid:48) ⊆ E andk(G(cid:48))denotesthenumberofconnectedcomponentsofG(cid:48). Viathisrelation, onecangeneralizeq frompositiveintegersto real andcomplexnumbers, asis necessarywhen analyzing zeros of P(G,q), called chromatic zeros. For a general graph G or family of graphs G , the calculation of the chromatic polynomial takes an exponentially long time. Planar m(cid:126) triangulations comprise a class that is particularly amenable to analysis, as we shall show. SinceatriangulationgraphG (whetherplanarornot)containsatleastonetriangle, P(G ,q) t t always contains the factor P(K ,q) = q(q−1)(q−2). (Here, K is the complete graph with 3 n n vertices, defined as the graph such that each vertex is adjacent to every other vertex by 1 an edge.) An interesting upper bound on an evaluation of a chromatic polynomial of a planar triangulation was derived by Tutte [3] (see also [4],[5]), namely 0 < |P(G ,τ +1)| ≤ U(n(G )) , (1.1) pt pt √ where τ = (1+ 5)/2 is the golden ratio and U(n) = τ5−n = (τ −1)n−5 . (1.2) As in [1], it is natural to define the ratio |P(G ,τ +1)| pt r(G ) ≡ , (1.3) pt U(n(G )) pt which is bounded above by 1. In this paper we shall present calculations of this ratio, and its limit as n → ∞, for a number of different families of planar triangulations. In [1] we showed that if p = 1, then, with m(cid:126) ≡ m, if P(G ,q) involves only a single power of a polynomial, pt,m (λ )m as in (2.8) below, it follows that r(G ) approaches zero exponentially rapidly as Gpt pt,m m → ∞. In [1] we also constructed one-parameter families G for which P(G ,q) is pt,m pt,m a sum of powers of certain terms λ with i = 1,2,3, given below in (3.1), then r(G ) i pt,m may approach a finite nonzero constant as m → ∞. We generalize these results here to the families G with p ≥ 2. We also exhibit a p = 1 family, denoted F , for which P(F ,q) is pt,m(cid:126) m m a sum of nonpolynomial λ s, i = 1,2,3, and show that for this family, r(F ) decreases to F,i m zero (exponentially rapidly) as m → ∞. It should be noted that the Tutte upper bound is satisfied as an equality by the triangle, K , but for planar triangulations with higher n, the 3 upper bound is realized as a strict inequality. PartofourworkconcernszerosofchromaticpolynomialsP(G ,q)forfamiliesofplanar pt,m(cid:126) triangulations G , i.e., chromatic zeros of these graphs. An interesting aspect of this study pt,m(cid:126) relates to an empirical observation made by Tutte in connection with his upper bound, namely that for a planar triangulation G , P(G ,q) typically has a real zero close to q = pt pt τ +1 = 2.6180339887.... This observation has been somewhat mysterious over the years, for at least two reasons. First, Tutte’s upper bound (1.1) does not imply that a P(G ,q) need pt haveazeroneartoτ+1. Second, itisknownthatforanarbitrary(loopless)graphG, P(G,q) √ √ cannot vanish exactly at q = τ +1 = (3+ 5 )/2. We recall the proof. If P(G,(3+ 5 )/2) √ were zero, then, since P(G,q) is a polynomial in q, it would have the factor [q−(3+ 5 )/2]. But since P(G,q) has rational coefficients (actually, integer coefficients, but all we use here is the property that they are rational), it would therefore also have to contain a factor √ involving the algebraic conjugate root, namely [q−(3− 5 )/2]. However, this would imply 2 √ that P(G,q) would also vanish at q = (3− 5 )/2 = 0.381966..., but this is impossible, since this point lies in an interval (0,1) where P(G,q) cannot vanish [6, 7]. As part of our analysis here, we shed some light on this mystery by constructing families of planar triangulation graphs G with p = 1 and p = 2 for which the chromatic polynomials have the respective pt,m(cid:126) forms P(G ,q) = c λm+c λm+c λm for p = 1 (with m ≡ m), where λ = q−2, pt,m Gpt,1 1 Gpt,2 2 Gpt,3 3 1 1 λ = q−3, and λ = −1, and P(G ,q) = (cid:80)3 (cid:80)3 c λm1λm2 for p = 2. We derive 2 3 pt,m(cid:126) i1=1 i2=1 Gpt,i1i2 i1 i2 properties of the coefficients c and show that P(G ,q) has a real chromatic zero that √ Gpt,(cid:126)i pt,m(cid:126) approaches (1/2)(3 + 5 ) as one or more of the m → ∞. We give the generalization of i this result to p ≥ 3. Further, we construct a one-parameter family of planar triangulations of this type with real zeros that approach 3 from below as m → ∞. II. GENERAL PROPERTIES OF ONE-PARAMETER FAMILIES OF PLANAR TRIANGULATIONS A. General We have constructed and studied various one-parameter families of planar triangulations G that can be built up in an interative (recursive) manner. (Here and below, for families pt,m where m(cid:126) is one-dimensional, we set m ≡ m to simplify the notation.) In this section we de- 1 rivegeneralpropertiesofthechromaticpolynomialsofthesefamiliesofplanartriangulations. For our families, the number of vertices is linearly related to m, n(G ) = αm+β , (2.1) pt,m where α and β are constants that depend on the type of family. We recall the Euler relation |V(G)|−|E(G)|+|F(G)| = χ = 2 for a graph G embedded on a surface of genus 0, such as E the plane, where χ is the Euler characteristic. In general, for a planar graph each of whose E faces has p sides, n(G), e(G), and f(G) satisfy the relations e(G) = p(n(G) − 2)/(p − 2) and f(G) = 2(n(G)−2)/(p−2). For the case of interest here, namely planar triangulation graphs, where each face is a triangle, it follows that e(G ) = 3(n(G )−2) (2.2) pt pt and f(G ) = 2(n(G )−2) , (2.3) pt pt so that e(G ) = (3/2)f(G ). pt pt 3 In our present study we will make use of several results that we derived in [1]. First, since U(n) → 0 as n → ∞ and since m is proportional to n, it follows that for these families of planar triangulations, lim P(G ,τ +1) = 0 . (2.4) pt,m m→∞ Second, given the upper bound (1.1) and the fact that U(n) approaches zero exponentially fast as n → ∞, it follows that P(G ,τ +1) approaches zero exponentially fast as m → ∞. (2.5) pt,m We recall two definitions that apply to any graph: (i) the degree d(v ) of a vertex v ∈ V i i is the number of edges that connect to it, and (ii) a k-regular graph is a graph for which all vertices have degree k. Since a triangulation graph G is not, in general, k-regular, it t is useful to define an effective vertex degree in the limit |V| → ∞. For this purpose, we introduce, as in our earlier work, the notation {G} for the formal limit n → ∞ of a family of graphs G. We define 2|E| d ({G}) = lim eff |V|→∞ |V| (cid:80) n d = i i i , (2.6) |V| where for a given G, n denotes the number of vertices with degree d and n(G) ≡ |V|. i i Substituting (2.2) in (2.6), we obtain d ({G }) = 6 . (2.7) eff pt We will use this below, in Sect. XIX. B. Families with P(G ,q) Consisting of a Power of a Single Polynomial pt,m There are several ways of constructing one-parameter families of planar triangulations. One method that we have used is the following, which produces families for which the chromatic polynomial involves a single power of a polynomial in q. Start with a basic graph G , drawn in the usual explicitly planar manner. The outer edges of this graph clearly pt,1 form a triangle, K . Next pick an interior triangle in G and place a copy of G in this 3 pt,1 pt,1 triangle so that the intersection of the resultant graph with the original G is the triangle pt,1 chosen. Denote this as G . Continuing in this manner, one constructs G with m ≥ 3. pt,2 pt,m ThechromaticpolynomialP(G ,q)iscalculatedfromP(G ,q)byusingthes = 3special pt,2 pt,1 4 case of the complete-graph intersection theorem. This theorem states that if for two graphs GandH (whicharenotnecessarilyplanarortriangulations), theintersectionG∩H = K for s some s, then P(G∪H,q) = P(G,q)P(H,q)/P(K ,q). (Note that P(K ,q) = (cid:81)s−1(q −j).) s s j=0 It follows that for planar triangulations formed in this interative manner, the chromatic polynomial has the form P(G ,q) = c (λ )m . (2.8) pt,m Gpt Gpt where the coefficient c and the term λ are polynomials in q that do not depend on m. Gpt Gpt Here and below, it is implicitly understood that m ≥ m , where m is the minimal value min min of m for which the family G is well defined. Since G contains at least one triangle, K , pt,m pt 3 the coefficient c contains (and may be equal to) P(K ,q) = q(q−1)(q−2). The chromatic Gpt 3 number of G may be 3 or 4. In the case of a planar triangulation which is a strip of the pt triangular lattice of length m vertices with cylindrical boundary conditions, to be discussed below, an alternate and equivalent way to construct the (m+1)’th member of the family is simply to add a layer of vertices to the strip at one end. C. Families with P(G ,q) Consisting of Powers of Several Functions pt,m We have also devised methods to obtain families of planar triangulations G with the pt,m(cid:126) property that the chromatic polynomial is a sum of more than one power of a function of q. We begin with the simplest case, p = 1, i.e., one-parameter families and then discuss families with p ≥ 2. For one-parameter families, we find the general structure jmax (cid:88) P(G ,q) = c (λ )m , (2.9) pt,m Gpt,j Gpt,j j=1 where m ≥ m and the c and λ are certain coefficients and functions depending min Gpt,j Gpt,j on q but not on m. Here we use the label G to refer to the general family of planar pt triangulations G . We will describe these methods below. Parenthetically, we recall that pt,m the form (2.9) is a general one for one-parameter recursive families of graphs, whether or not they are planar triangulations [11], [8]. For (2.9) evaluated at a given value q = q , 0 as m → ∞, and hence n → ∞, the behavior of P(G ,q) is controlled by which λ pt,m Gpt,j is dominant at q = q , i.e., which of these has the largest magnitude |λ (q )|. For our 0 Gpt,j 0 purposes, a q of major interest is τ +1, since the Tutte upper bound (1.1) applies for this 0 value. We denote the λ that is dominant at q = τ +1 as λ . Clearly, if P(G ,q) Gpt,j Gpt,dom pt,m involves only a single power, as in (2.8), then λ = λ . Gpt,dom Gpt As in earlier works [8–10], it can be convenient to obtain the chromatic polynomials P(G ,q) via a Taylor series expansion, in an auxiliary variable x, of a generating function pt,m 5 Γ(G ,q,x). Below, we will have occasion to use this method for the family F (see (18.4)). pt m Both the form (2.9) and the expression via a generating function are equivalent to the property that P(G ,q) satisfies a recursion relation, for m ≥ j +m : pt,m max min jmax (cid:88) P(G ,q)+ b P(G ,q) = 0 , (2.10) pt,m Gpt,j pt,m−j j=1 where the b , j = 1,...j , are given by Gpt,j max jmax jmax (cid:88) (cid:89) 1+ b xj = (1−λ x) . (2.11) j Gpt,j j=1 j=1 Thus, jmax (cid:88) b = − λ , (2.12) Gpt,1 Gpt,j j=1 jmax (cid:88) b = λ λ , (2.13) Gpt,2 Gpt,j Gpt,k j=1, k=1, j(cid:54)=k and so forth, up to jmax (cid:89) b = (−1)jmax λ . (2.14) Gpt,jmax Gpt,j j=1 D. Asymptotic Behavior as m → ∞ In [1] we discussed the asymptotic behavior of the chromatic polynomials as m → ∞. In both the cases of Eq. (2.8) and (2.9), a single power [λ ]m dominates the sum as m → ∞. Gpt,j For a member of a one-parameter family of planar triangulations, G , we use the notation pt,m r(G ) for the ratio (1.3), and we define pt,m r(G ) ≡ lim r(G ) . (2.15) pt,∞ pt,m m→∞ We define the (real, non-negative) constant a as [1] Gpt |λ (τ +1)|1/α a = lim[r(G )]1/n = Gpt,dom . (2.16) Gpt n→∞ pt,m τ −1 We showed in [1] that if j = 1, then a < 1 and hence for the classes of G under max Gpt pt,m consideration, (i) r(G ) = 0 and (ii) r(G ) decreases toward zero exponentially rapidly pt,∞ pt,m 6 as a function of m and n as m → ∞. Note that this does not imply that P(G ,q) has a pt,m zero that approaches q = τ +1 as m, n → ∞. For one-parameter families of planar triangulation graphs G where P(G ,q) has the pt,m pt,m form (2.9) with j ≥ 2, a consequence of the Tutte upper bound (1.1) is that as m → ∞, max any contribution c (λ )m in (2.9), when evaluated at q = τ +1, must be less than or Gpt,j Gpt,j equal in magnitude to (τ −1)n−5. Therefore, for a given j in this case, either the coefficient c vanishes for q = τ +1 or, if this coefficient does not vanish at q = τ +1, then, taking Gpt,j into account the relation (2.1), it follows that |λ |1/α Gpt,j ≤ 1 at q = τ +1 ∀ j . (2.17) τ −1 If this inequality is realized as an equality, then r(G ) is a nonzero constant, which nec- pt,∞ essarily lies in the interval (0,1), so that a = 1. For the families G for which m and Gpt pt,m n are linearly related, as specified in (2.1), this type of behavior occurs if and only if, when P(G ,q) is evaluated at q = τ +1, the (necessarily) dominant λ (with nonvanishing pt,m Gpt,j coefficient c ), is equal to τ −1 in magnitude, i.e., |λ | = τ −1 at q = τ +1. This is Gpt,j Gpt,dom true, in particular, if this λ = q −2. In the structural form (3.16) below, we shall label Gpt,j this as the j = 1 term. It is a general property that if a graph G contains a complete graph K as a subgraph, p then P(G,q) contains the factor P(K ,q). In particular, a triangulation graph, whether p planar or not, has the factor P(K ,q) and a planar triangulation may also contain a K . 3 4 (However, by Kuratowski’s Theorem, a planar graph may not contain a K with p ≥ 5.) p Thus, for a planar triangulation G , P(G ,q) = 0 for q = 0, 1, 2. If G ⊇ K , then pt pt pt 4 P(G ,q) also vanishes at q = 3. If P(G ,q) has the form of a single power, given as Eq. pt pt (2.8), then these factors are explicit. If, however, P(G ,q) has the form of a sum of j ≥ 2 pt max powers [λ ]m, then the conditions that P(G ,q) vanish at q = 0, 1, 2 imply relations Gpt,j pt between the various terms. Moreover, the condition that P(G ,τ + 1) obeys the Tutte pt,m upper bound (1.1) also implies conditions on the structure of this chromatic polynomial. We derive these next. 7 III. PROPERTIES OF A CLASS OF G WITH P(G ,q) HAVING j = 3 pt,m pt,m max AND CERTAIN λ Gpt,j A. Structure of Coefficients c in P(G ,q) Gpt,j pt,m For a large class of one-parameter families of planar triangulations that we have con- structed and studied, for which P(G ,q) has the form (2.9), we find that (i) j = 3 and pt,m max (ii) the λ ≡ λ with j = 1, 2, 3 have the form Gpt,j j λ = q −2, λ = q −3, λ = −1 . (3.1) 1 2 3 For this class of planar triangulations, we can derive some general results concerning the functional form of the coefficients c (where we will often suppress the subscript pt on G Gpt,j pt where the meaning is obvious). Using the general form (2.9) with j = 3 and these λ ’s, max j we can derive the following identities. The fact that P(G ,0) = 0 implies that pt c (−2)m +c (−3)m +c (−1)m = 0 . (3.2) G,1 G,2 G,3 where for ease of notation we suppress the subscript pt on G here and in related equations. pt Since this equation must hold for arbitrary m (understood implicitly to be an integer in the range m ≥ m , where m is the minimal value for which the family G is well min min pt,m defined), it implies that c = 0 for all j. Hence, for these families, G,j c contains the factor q for j = 1, 2, 3 . (3.3) G,j The evaluation P(G ,1) = 0 reads pt c (−1)m +c (−2)m +c (−1)m = 0 at q = 1 . (3.4) G,1 G,2 G,3 Since this equation must hold for arbitrary m ≥ m , it implies two conditions on the min evaluation of the coefficients at q = 1, namely c = 0 and c +c = 0 at q = 1 . (3.5) G,2 G,1 G,3 In particular, (3.5) implies that c contains the factor q −1 . (3.6) G,2 The evaluation P(G ,2) = 0 reads pt c 0m +[c +c ](−1)m = 0 at q = 2 . (3.7) G,1 G,2 G,3 8 Since this equation holds for arbitrary m ≥ m , it implies that min c +c = 0 at q = 2 . (3.8) G,2 G,3 If a family G which has m = 0, (3.7) and (3.8) together would also imply that c = 0 pt,m min G,1 at q = 2. Continuing with P(G ,q) of the form (2.9) with (3.1), we next analyze the evaluation of pt,m P(G ,q) at q = τ+1, viz., P(G ,τ+1). Since τ−1 = 0.61803... and τ−2 = −0.381966 pt,m pt,m are smaller than unity in magnitude, the first two terms in P(G ,τ +1) vanish exponen- pt,m tially rapidly as m increases. As regards the ratio r(G ), as m increases, the contribution pt,m of the first term to this upper bound approaches a constant, while the contribution of the second term vanishes exponentially rapidly. Given the relation (2.1), the Tutte upper bound also vanishes exponentially rapidly as a function of m. Therefore, in order for P(G ,τ+1) pt,m to satisfy the Tutte upper bound (1.1), it is necessary and sufficient that c = 0 at q = τ +1 . (3.9) G,3 This means that √ (cid:16)3+ 5 (cid:17) c contains the factor q − . (3.10) G,3 2 Giventhatachromaticpolynomialhasrational(actuallyinteger)coefficientsasapolynomial in q, this means that c must also contain a factor involving the algebraically conjugate G,3 root, i.e., √ (cid:16)3− 5 (cid:17) c contains the factor q − . (3.11) G,3 2 Combining these, we derive the result that c contains the factor q2 −3q +1 . (3.12) G,3 Having proved these results, it is thus convenient to extract the factors explicitly and define c G,1 κ ≡ , (3.13) G,1 q c G,2 κ ≡ , (3.14) G,2 q(q −1) and c G,3 κ ≡ . (3.15) G,3 q(q2 −3q +1) For this class of planar triangulation graphs G , we thus have the general structural pt,m formula (cid:104) P(G ,q) = q κ (q −2)m +κ (q −1)(q −3)m pt,m G,1 G,2 9