ISSN:
0219-3094
Schlagwort(e):
05C99
;
square lattice
;
Tutte polynomial
;
forest
;
acyclic orientation
;
chromatic polynomial
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01608795
Permalink
