ISSN:
0219-3094
Keywords:
05C99
;
square lattice
;
Tutte polynomial
;
forest
;
acyclic orientation
;
chromatic polynomial
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01608795
Permalink
