PERFECT MATCHINGS AND PERFECT SQUARES

[摘要] In 1961, P. W. Kasteleyn enumerated the domino tilings of a 2n x 2n chessboard. His answer was always a square or double a square (we call such a number ''squarish''), but he did not provide a combinatorial explanation for this. In the present thesis, we prove by mostly combinatorial arguments that the number of matchings of a large class of graphs with 4-fold rotational symmetry is squarish; our result includes the squarishness of Kasteleyn's domino tilings as a special case and provides a combinatorial interpretation for the square root. We then extend our result to graphs with other rotational symmetries. (C) 1994 Academic Press, Inc.

[发布日期] 1994-07-01