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 then ×n section of the square lattice together with some properties of the structure of the random forest. There are, however, many unanswered questions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
N. Alon, A.M. Frieze, and D.J.A. Welsh, Polynomial time randomised approximation schemes for Tutte-Grothendieck invariants: The dense case, Random Struct. Algorithms6 (1995) 459–478.
A. Andrzejak, An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Math.190 (1998) 39–54.
J.D. Annan, A randomised approximation algorithm for counting the number of forests in dense graphs, Combin. Prob. Comput.3 (1994) 273–283.
A.V. Bakaev and V.I. Kabanovich, Series expansions for theq-colour problem on the square and cubic lattices, J. Phys. A27 (1994) 6731–6739.
F. Berman et al., Generalized planar matching, J. Algorithms11 (1990) 153–184.
N.L. Biggs, Chromatic and thermodynamic limits, J. Phys. A8 (1975) L 110–112.
N.L. Biggs, Colouring square lattice graphs, Bull. London Math. Soc.9 (1977) 54–56.
N.L. Biggs and G.H.J. Meredith, Approximations for chromatic polynomials, J. Combin. Theory Ser. B20 (1976) 5–19.
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.
C.M. Fortuin and P.W. Kasteleyn, On the random cluster model. I. Introduction and relation to other models, Physica57 (1972) 536–564.
M.R. Garey and D.S. Johnson, The rectilinear Steiner problem is NP-complete, SIAM J. Appl. Math.32 (1977) 826–834.
M.R. Garey and D.S. Johnson, Computers and Intractability — A Guide to the Theory of NP-completeness, W.H. Freeman, San Francisco, 1979.
G.R. Grimmett, Multidimensional lattices and their partition function, Quart. J. Math. Oxford29 (1978) 141–157.
G.R. Grimmett, The rank polynomials of large random lattices, J. London Math. Soc.18 (1978) 567–575.
A. Itai, C.H. Papadimitriou, and J.L. Szwarcfiter, Hamilton paths in grid graphs, SIAM J. Comput.11 (1982) 676–686.
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.
M. Jerrum, A very simple algorithm for estimating the number ofk-colourings of a low-degree graph, Random Struct. Algorithms7 (1995) 157–165.
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.
D.S. Johnson, The NP-completeness column: An ongoing guide, J. Algorithms6 (1985) 434–451.
N.E. Kahale and L.J. Schulman, Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph, Combinatorica16 (1996) 383–397.
D. Kim and I.G. Enting, The limit of chromatic polynomials, J. Combin. Theory Ser. B26 (1979) 327–336.
E. Lieb, The residual entropy of square ice, Phys. Rev.162 (1967) 162–172.
L. Lovász, Combinatorial Problems and Exercises, North-Holland Pub. Co., Amsterdam, 1979, pp. 238–243.
D.B. Massey et al., Lê numbers of arrangements and matroid identities, J. Combin. Theory Ser. B70 (1997) 118–133.
C.J.H. McDiarmid, Private communication.
J.F. Nagle, A new subgraph expansion for obtaining coloring polynomials for graphs, J. Combin. Theory Ser. B10 (1971) 42–59.
S. Noble, Evaluating the Tutte polynomial for graphs of bounded tree-width, Combin. Prob. Comput.7 (3) (1998) 307–322.
J.G. Propp and D.B. Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Struct. Algorithms9 (1996) 223–252.
N. Robertson and P.D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms7 (1986) 309–322.
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.
R.P. Stanley, Acyclic orientations of graphs, Discrete Math.5 (1973) 171–178.
H.N.V. Temperley, Combinatorics, London Mathematical Society Lecture Notes Series, Vol. 13, Cambridge University Press, 1974, pp. 202–204
C.J. Thompson, Mathematical Statistical Mechanics, Princeton University Press, Princeton, 1979, pp. 131–135.
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.
D.J.A. Welsh, Complexity: Knots, Colourings and Counting, London Mathematical Society Lecture Notes Series, Vol. 186, Cambridge University Press, 1993.
Author information
Authors and Affiliations
Additional information
Supported by a grant from D.G.A.P.A.
Supported in part by Esprit Working Group No. 21726, “RAND2”.
Rights and permissions
About this article
Cite this article
Merino, C., Welsh, D.J.A. Forests, colorings and acyclic orientations of the square lattice. Annals of Combinatorics 3, 417–429 (1999). https://doi.org/10.1007/BF01608795
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01608795