Tutte Polynomials in Square Grids

Marc Noy

Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya

Algorithms Seminar

December 16, 1999

[summary by Frédéric Chyzak]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract
The Tutte polynomial of a graph G is a two-variable polynomial that records much information on G. In particular, different evaluations at integers provide the number of spanning trees, forests (acyclic spanning subgraphs), and acyclic orientations of G. We estimate these values when G is an n× n square grid so as to deduce refined upper and lower bounds for the numbers of forests and acyclic orientations on such grids.



1   Polynomial Invariants of Graphs

1.1   Chromatic polynomials

A general graph G=(V,E) is a undirected graph with loops and multiple edges allowed; it is described by its set V of vertices and its set E of edges. The chromatic polynomial p(G;l), introduced by Birkhoff in 1912 is a very important invariant of G: it counts the number of its l-colourings, i.e., the number of ways to assign colours to the vertices of G in such a way that no two adjacent vertices share the same colour, and that the number of colours used is at most l. This polynomial records many statistics of the graph: indeed, for a graph on n vertices, we have the expansion p(G;l)=ln-|E|ln-1+aln-2-...±lk(G) where a=|E|(|E|-1)/2-t(G) relates to the number t(G) of triangles in G, and where k(G) is the number of connected components of G. Also, the coefficients of p(G;l) alternate in signs. Table 1 provides other interesting graph statistics as evaluations of the chromatic polynomial.

Unfortunately, the computation of a chromatic polynomial is hard: already the problem of computing the chromatic number of a graph G, i.e., the smallest integer l such that there exists a l-colouring, is NP-complete; evaluating the chromatic polynomial itself is #P-hard, as is even computing the chromatic polynomial at any algebraic number different from 0, 1, and 2. A simple exponential algorithm to compute p(G;l) is based on contraction and deletion of edges: the graph G /  e resulting from the contraction of an edge e in a graph G is obtained by removing the edge and identifying both incident vertices; the mere deletion of an edge e in a graph G results in the graph G\ e with same vertex set V and new edge set E\{e}. The algorithm consists in following the recurrence p(G;l)=p(G\ e;l)-p(G /  e;l) provided that G is connected and that e is neither a loop nor a bridge (also called isthmus or co-loop, i.e., an edge whose deletion does not disconnect the graph). Finally, the chromatic polynomial of a (possibly disconnected) graph is the product of the chromatic polynomials of its connected components.

p(G;0) 0
p(G;1) 1 if G is empty
p(G;1) 0 if G contains an edge
p(G;2) 2k(G) if G is bipartite
p(G;2) 0 if G is not bipartite
|p(G;-1)| # of acyclic orientations [4]
.8cm
T(G;1,1) # of spanning trees
T(G;2,1) # of forests
T(G;1,2) # of connected subgraphs
T(G;2,0) # of acyclic orientations [4]
T(G;1,0) # of ac. or. with a single source
T(G;0,2) # of totally cyclic orientations




Table 1: Special evaluations of the chromatic (left) and Tutte (right) polynomials.

1.2   Tutte polynomials

A generalization of the chromatic polynomial is the Tutte polynomial T(G;x,y) of a graph G [5, 6], most easily defined as the variant T(G;x,y)=R(G;x-1,y-1) of Whitney's rank generating function R(G;x,y) [9]. The rank of a graph G is defined as the size of any of its spanning forests, which is |V|-k(G). This notion stems from the matroid interpretation of graphs [7, 8], which, informally, views circuits (i.e., cycles) in a graph as dependency relations and forests as sets of independent edges. Now, by definition
R(G;x,y)=
 
å
AÍ E
xr(E)-r(A)y|A|-r(A) =xr(E)
 
å
AÍ E
y|A|/(xy)r(A),     (1)
where r(A) denotes the rank of the subgraph GA=(V,A) of the graph G=(V,E) obtained by retaining the subset AÍ E of its edges only. Note that r(A)=r(E) means that GA has the same number of connected components as G, while r(A)=|A| means that GA is acyclic. The chromatic polynomial is recovered through the relation p(G;l)=(-1)r(G)lk(G)T(G;1-l,0); on the other hand, the relation f(G;l)=(-1)|G|T(G;0,1-l) defines the flow polynomial of G, which counts the number of flows on G with edges weighted by elements of Z/lZ, once any orientation has been chosen on G. (A flow is an assignment of weights to edges in such a way that the weights corresponding to all edges incident to the same vertex add up to zero.) Table 1 provides other interesting graph statistics as evaluations of the Tutte polynomial.

An algorithm similar to the one in the case of the chromatic polynomial above computes the Tutte polynomial, and is based on the relations: T(G;x,y)=1 if G is empty; T(G;x,y)=T(G /  e;x,y) if e is a bridge; T(G;x,y)=T(G\ e;x,y) if e is a loop; and T(G;x,y)=T(G /  e;x,y)+T(G\ e;x,y) otherwise. Finally, the Tutte polynomial of a (possibly disconnected) graph is the product of the Tutte polynomials of its connected components.

1.3   Tutte--Grothendieck invariants

A restatement of this is that the Tutte polynomial is an example of Tutte--Grothendieck invariant [2], i.e., a function v from the set of graphs to a fixed commutative ring---Z[x,y] in the case of the Tutte polynomial---with the relations:
  1. v(G)=v(G /  e)+v(G\ e) provided G is connected and e is neither a loop nor a bridge;
  2. the invariant of a graph is the product of the invariants of its connected components;
  3. the invariants of two isomorphic graphs are the same.
A result by Brylawski [2] is that any Tutte--Grothendieck invariant is uniquely determined by its values on the loop and bridge graphs, consisting of a single loop around a single vertex and of a single edge between two vertices, respectively, and the invariant v(G) is the evaluation of the Tutte polynomial at x=v(loop graph) and y=v(bridge graph).

The Tutte polynomial satisfies the following more general universality theorem (cf. [1, Chap. X]). Let v be any function from the set of graphs to the commutative ring Z[x,y,a,s,t] which satisfies conditions 2. and 3. in the description of Tutte--Grothendieck invariants and the relations u(G)=a|G| if G is empty; u(G)=xu(G /  e) if e is a bridge; u(G)=yu(G\ e) if e is a loop; u(G)=s u(G\ e)+t u(G /  e) otherwise. Then v is given in terms of the Tutte polynomial of G by the relation v(G)=ak(G)s|G|tr(G)T(G;a x/t,y/s). Special cases are the chromatic and Tutte polynomials, respectively obtained when (x,y,a,s,t) is set to (1-x,0,x,1,-1) and (x,y,1,1,1).

1.4   Matroidal interpretation of graphs

Matroids [7, 8] are a general concept used to represent the combinatorics of dependency between objects of many different types, like linear dependency, affine dependency, algebraic dependency, the structure of cycles (or circuits) in a graph, and so on. Chromatic and Tutte polynomials extend to this setting with the same type of properties. Applications include lattice theory, graph theory, knot theory, coding theory, geometry, networks, percolation theory, and statistical mechanics.

2   Counting Problems on the n× n Grid

Although the following combinatorial objects are well-defined on any graph, we consider their enumeration on the square n× n grid Ln (with simple edges only) where we proceed to derive new asymptotic estimates:
  1. A matching is a pairing of neighbouring vertices by edges of the graph, possibly leaving some of its vertices unpaired. Enumerating matchings relates to the study of a lattice gas model of statistical physics for a gas consisting of monomers and dimers.
  2. A perfect matching is a matching that leaves no vertex on its own. This corresponds to a gas with dimers only.
  3. A set of vertices is independent if no two of them can be joined by an edge. This corresponds to Fibonacci arrays, i.e., arrays consisting of 0's and 1's only, with no two consecutive 1's, either vertically or horizontally.
  4. A spanning tree is a tree made of edges of the graph and that exhausts its vertices.
  5. An acyclic orientations is an orientation of the edges of the graph that induces no cycle.
Upon substitution of each vertex of Ln by a square centred at this vertex, and after gluing squares that correspond to adjacent vertices, a matching becomes a tiling with dominoes and squares while a perfect matching becomes a domino tiling. Obviously, the above-mentioned transformation is a one-to-one correspondence. The following combinatorial algorithm by Temperley provides another bijection, between spanning trees on Ln and perfect matchings on L2n+1 deprived of one vertex: (i) spanning trees are rooted at some fixed vertex; (ii) dominoes are then placed on the branches of trees, from leaves to the root, and the same process is applied to the dual graph of the tree; (iii) domino tilings are changed into perfect matchings. The common counting number t(n) on the grid Ln is given as T(Ln;1,1) (see Table 1) and is known to satisfy limn®¥t(n)1/n2=t where t=3.2099125...

Upper and lower bounds for forests and acyclic orientations

The numbers of forests and acyclic orientations on the graph Ln are expressable in terms of its Tutte polynomial, and are T(Ln;2,1) and T(Ln;2,0), respectively (see Table 1). Since a spanning tree is a forest and a forest is merely an unconstrained choice of edges, the bounds tn<fn<22n(n-1)<4n2 hold for the number of forests. On the other hand, orienting all vertical edges towards the top endows Ln with an acyclic orientation, and acyclic orientations are orientations. This yields the bounds 2n(n-1)<an<22n(n-1)<4n2. Again, the limits f=limn®¥f(n)1/n2 and a=limn®¥a(n)1/n2 exist; the relations above yield the trivial bounds t=3.2099125...<f<4 and 2<a<4. Merino, Noy, and Welsh have obtained the improved bounds
t=3.64497£ f£3.74698  and  3.41358£ a£3.56322.

The method used to derive the new, better upper bounds is to view the square grid Ln as a composite of m/n rectangular m× n grids Lm,n, relying on the computation of T(Lm,n;2,1) as the cardinal of a rational language. The idea is to extend a forest, respectively an acyclic orientation, on Lm,n to one on Lm,n+1. To this end, the m vertices on the nth column of the original graph are tagged in order to keep track of vertices that are members of the same tree. The number of such configurations is finite (in particular, the m vertices can be in at most m different trees). Among the 22m-1 choices of edges that may be used to extend the original graph, only part of them do not produce a cycle. This provides a finite-state automaton that recognizes the relevant configurations on Lm,n. The generating series that enumerates this configurations is thus rational, and the counting numbers grow as the exponential amn of an algebraic number am. Gluing n/m configurations on Lm,n in any way yields the upper bounds fn£(amn)n/m2n(n/m-1)£(2am/m)n2 (since blind gluing may produce cycles), as well as similar bounds for an (with a different am).

The case of the new lower bounds is very similar. Again, the forests, resp. acyclic orientations, on Ln are obtained by gluing relevant configurations on Lm,n. However, an additional constraint is that the selected configurations on Lm,n induce forests, resp. acyclic orientations, on the graph Lm,n* obtained by contracting the mth row to a single vertex. This ensures that no cycle is created while gluing the rectangular grids. Again, the configurations on Lm,n* are counted by a rational language, yielding lower bounds of the same form as the upper bounds above. The numerical values indicated were obtained for m=8. An article is in preparation [3].

3   Computing the Tutte Polynomial of Lm,n by a Recurrence in n

The interpretation in terms of rational languages also applies to the computation of Tutte polynomials for Lm,n, based on the right-most representation (1) of Whitney's rank generating function. This form makes explicit the way to extend the rational automaton recognizing the forests of Lm,n, which has been described in the previous section. This extension only needs to keep track of the number of vertices (+m at each column), the number of connected components (whose variation is between -m and +m at each column), and the number of edges (which by difference yields the rank). To each state s corresponding to a structure of connected components on the nth column of Lm,n, we associate a generating function F(s)(x,y,z)=ånRn(s)(x,y)zn where Rn(s)(x,y) is the contribution to the sum (1) restricted to configurations A of edges whose last column corresponds to state s. This induces a linear system of recurrences between the F(s)(x,y,z), with Laurent polynomial entries in x and y.

For fixed m, the rational generating function of the rank generating functions of the family of graphs Lm,n is thus obtained as one of the F(s)(x,y,z) for a suitable state s. The rational generating function of the Tutte polynomials is then obtained by shifting x and y.

References

[1]
Bollobás (Béla). -- Modern graph theory. -- Springer-Verlag, New York, 1998, xiv+394p.

[2]
Brylawski (Thomas H.). -- A decomposition for combinatorial geometries. Transactions of the AMS, vol. 171, 1972, pp. 235--282.

[3]
Calkin (N.), Merino (C.), Noble (S.), and Noy (M.). -- Improved bounds for the number of forests and acyclic orientations in the square lattice. -- In preparation.

[4]
Stanley (Richard P.). -- A chromatic-like polynomial for ordered sets. In Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C., 1970), pp. 421--427. -- Univ. North Carolina, Chapel Hill, N.C., 1970.

[5]
Tutte (W. T.). -- A ring in graph theory. Proceedings of the AMS, vol. 43, 1947, pp. 26--40.

[6]
Tutte (W. T.). -- A contribution to the theory of chromatic polynomials. Canadian Journal of Mathematics, vol. 6, 1954, pp. 80--91.

[7]
Welsh (D. J. A.). -- Matroids: fundamental concepts. In Handbook of combinatorics, Vol. 1, pp. 481--526. -- Elsevier, Amsterdam, 1995.

[8]
Welsh (Dominic). -- Colouring problems and matroids. In Surveys in combinatorics (Proc. Seventh British Combinatorial Conf., Cambridge, 1979), pp. 229--257. -- Cambridge University Press, Cambridge, 1979.

[9]
Whitney (Hassler). -- The coloring of graphs. Annals of Mathematics, vol. 33, 1932, pp. 688--718.
This document was translated from LATEX by HEVEA.