Annals of Combinatorics 3 (1999) 417-429

Forests, Colorings and Acyclic Orientations of the Square Lattice

C. Merino and D.J.A. Welsh

Mathematical Institute, 24--26 St. Giles, Oxford University, OX1 3LB, UK
{merino, dwelsh}

Received December 11, 1998

AMS Subject Classification: 05C99

Abstract. There is no known polynomial time algorithm which generates a random forest or counts forests or acyclic orientations in general graphs. On the other hand, there is no technical reason why such algorithms should not exist. These are key questions in the theory of approximately evaluating the Tutte polynomial which in turn contains several other specializations of interest to statistical physics, such as the Ising, Potts, and random cluster models. Here, we consider these problems on the square lattice, which apart from its interest to statistical physics is, as we explain, also a crucial structure in complexity theory. We obtain some asymptotic counting results about these quantities on the n×n section of the square lattice together with some properties of the structure of the random forest. There are, however, many unanswered questions.

Keywords: square lattice, Tutte polynomial, forest, acyclic orientation, chromatic polynomial


1.  N. Alon, A.M. Frieze, and D.J.A. Welsh, Polynomial time randomised approximation schemes for Tutte-Grothendieck invariants: The dense case, Random Struct. Algorithms 6 (1995) 459–478.

2.  A. Andrzejak, An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Math. 190 (1998) 39–54.

3.  J.D. Annan, A randomised approximation algorithm for counting the number of forests in dense graphs, Combin. Prob. Comput. 3 (1994) 273–283.

4.  A.V. Bakaev and V.I. Kabanovich, Series expansions for the $q$-colour problem on the square and cubic lattices, J. Phys. A 27 (1994) 6731–6739.

5.  F. Berman et al., Generalized planar matching, J. Algorithms 11 (1990) 153–184.

6.  N.L. Biggs, Chromatic and thermodynamic limits, J. Phys. A 8 (1975) L 110–112.

7.  N.L. Biggs, Colouring square lattice graphs, Bull. London Math. Soc. 9 (1977) 54–56.

8.  N.L. Biggs and G.H.J. Meredith, Approximations for chromatic polynomials, J. Combin. Theory Ser. B 20 (1976) 5–19.

9.  T.H. Brylawski and J.G. Oxley, The Tutte polynomial and its applications, In: Matroid Applications, N. White, Ed., Cambridge University Press, 1992, pp. 123–225.

10.  C.M. Fortuin and P.W. Kasteleyn, On the random cluster model. I. Introduction and relation to other models, Physica 57 (1972) 536–564.

11.  M.R. Garey and D.S. Johnson, The rectilinear Steiner problem is NP-complete, SIAM J. Appl. Math.~{\bf 32} (1977) 826–834.

12.  M.R. Garey and D.S. Johnson, Computers and Intractability --- A Guide to the Theory of NP-completeness, W.H. Freeman, San Francisco, 1979.

13.  G.R. Grimmett, Multidimensional lattices and their partition function, Quart. J. Math. Oxford 29 (1978) 141–157.

14.  G.R. Grimmett, The rank polynomials of large random lattices, J. London Math. Soc. 18 (1978) 567–575.

15.  A. Itai, C.H. Papadimitriou, and J.L. Szwarcfiter, Hamilton paths in grid graphs, SIAM J. Comput. 11 (1982) 676–686.

16.  F. Jaeger, D.L. Vertigan, and D.J.A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Camb. Phil. Soc. 108 (1990) 35–53.

17.  M. Jerrum, A very simple algorithm for estimating the number of $k$-colourings of a low-degree graph, Random Struct. Algorithms 7 (1995) 157–165.

18.  M. Jerrum, Mathematical foundations of Markov chain Monte Carlo method, In: Probabilistic Methods for Algorithmic Discrete Mathematics, M. Habib et al., Eds., Algorithms and Combinatorics, Vol. 16, Springer-Verlag, 1998, pp. 116–165.

19.  D.S. Johnson, The NP-completeness column: An ongoing guide, J. Algorithms 6 (1985) 434–451.

20.  N.E.~Kahale and L.J.~Schulman, Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph, Combinatorica 16 (1996) 383–397.

21.  D. Kim and I.G. Enting, The limit of chromatic polynomials, J. Combin. Theory Ser. B 26 (1979) 327–336.

22.  E. Lieb, The residual entropy of square ice, Phys. Rev. 162 (1967) 162–172.

23.  L. Lovász, Combinatorial Problems and Exercises, North-Holland Pub. Co., Amsterdam, 1979, pp. 238–243.

24.  D.B. Massey et al., Lènumbers of arrangements and matroid identities, J. Combin. Theory Ser. B 70 (1997) 118–133.

25.  C.J.H. McDiarmid, Private communication.

26.  J.F. Nagle, A new subgraph expansion for obtaining coloring polynomials for graphs, J. Combin. Theory Ser. B 10 (1971) 42–59.

27.  S. Noble, Evaluating the Tutte polynomial for graphs of bounded tree-width, Combin. Prob. Comput. 7 (3) (1998) 307–322.

28.  J.G. Propp and D.B. Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Struct. Algorithms 9 (1996) 223–252.

29.  N. Robertson and P.D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms 7 (1986) 309–322.

30.  J. Salas and A.D. Sokal, Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem, J. Stat. Phys. 86 (1997) 551–579.

31.  R.P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973) 171–178.

32.  H.N.V. Temperley, Combinatorics, London Mathematical Society Lecture Notes Series, Vol. 13, Cambridge University Press, 1974, pp. 202–204.

33.  C.J.~Thompson, Mathematical Statistical Mechanics, Princeton University Press, Princeton, 1979, pp. 131–135.

34.  D.L. Vertigan and D.J.A.~Welsh, The computational complexity of the Tutte plane: The bipartite case, Combin. Prob. Comput. 1 (1992) 181–187.

35.  D.J.A. Welsh, Complexity: Knots, Colourings and Counting, London Mathematical Society Lecture Notes Series, Vol. 186, Cambridge University Press, 1993.

Get the DVI| PS | PDF file of this abstract.