Perfect matchings, spanning trees, plane partitions and statistical physics.
Mihai Ciucu · Deep Blue (University of Michigan) · 1996
This thesis is concerned with perfect matchings of graphs and is organized in three parts. In the first chapter we introduce "cellular graphs," i.e., graphs whose edges can be partitioned into 4-cycles so that at most two 4-cycles meet at a vertex. We then present a "Reduction Theorem" for the number of matchings of certain subgraphs of cellular graphs. This generalizes a result of Elkies, Kuperberg, Larsen and Propp stating that the number of perfect matchings of the Aztec diamond of order n is 2$\sp{n(n+1)/2}$. Other applications of the Reduction Theorem include the proof of a special case of a conjecture of T. Y. Chow on spanning trees of alternating strips and a combinatorial enumeration of the matchings of fortress graphs, first obtained (algebraically) by B-Y. Yang. The material in the second chapter is organized in a similar manner, this time with a "Factorization Theorem" as the centerpiece, followed by a number of applications. A planar bipartite graph G invariant under reflection across some straight line l is called symmetric if the set of vertices on l separates G. Let M(G) denote the matching generating function of the graph G. Given a symmetric graph G, the Factorization Theorem states that M(G) equals a power of 2 times $M(G\sp+)M(G\sp-)$, where $G\sp+$ and $G\sp-$ are certain easily constructible subgraphs of G. As a direct corollary, we obtain a counterpart of the squarishness theorem of W. Jockusch. As further applications of our result, we enumerate the perfect matchings of several families of graphs and we obtain new solutions for the enumeration of two of the ten symmetry classes of plane partitions (namely, transposed complementary and cyclically symmetric, transposed complementary) contained in a given box. Finally, we consider symmetry classes of perfect matchings of the Aztec diamond graph and we solve the previously open problem of enumerating the matchings that are invariant under rotation by 90 degrees. In the last chapter we construct hypergraphs that can be regarded as higher dimensional analogs of the Aztec diamonds. We also consider a certain d-dimensional statistical model (which we call the (2$\sp{d}$ + 2)-vertex model) whose free energy is closely related to the number of matchings of the constructed hypergraphs. We prove that the limit defining the free energy of the (2$\sp{d}$ + 2)-vertex model exists and we obtain bounds for it. As a consequence, we obtain an especially good asymptotical approximation for the number of matchings of our hypergraphs.