Ciucu 9802390 This project is concerned with the enumeration of perfect matchings of certain special graphs that turn out to be closely related to several important problems in combinatorics (enumeration of spanning trees, plane partitions, alternating sign matrices), and also have strong connections with interesting questions in probability (rapidly mixing Markov chains) and statistical physics (dimer models and vertex models). Specifically, based on the solution the PI found for an open spanning tree enumeration problem posed by Stanley, the PI intends to extend the ideas in his previous work on the factorization theorem for perfect matchings of symmetric graphs to obtain similar factorizations for characteristic polynomials of graphs and, as a consequence, for spanning trees. Furthemore, the PI intends to use ideas from his work on the complementation theorem for perfect matchings to classify periodic weightings of the Aztec diamond that lead to nice enumeration formulas. This would give a unified perspective on several results of Elkies, Kuperberg, Larsen and Propp, B. Y. Yang, Stanley and the PI. In addition to the core research program outlined above, the PI intends to pursue three additional problems. First, the PI will pursue extending comparison results of Diaconis and Saloff-Coste to non-reversible Markov chains. This would allow one to deduce the rapid mixing of the elementary move Markov chain on certain three dimensional ``lozenge'' tilings, considered by the PI as an analog of the two dimensional situation studied by Luby, Randall and Sinclair. Second, the PI will continue his investigations of the three dimensional dimer problem by considering, besides the simple cubic lattice, other lattices of comparable interest (e.g., the body-centered cubic lattice or the face-centered cubic lattice), as well as some other problems likely to be suitable for such an analysis (e.g., three-colorings of the cubic lattice). And third, the PI intends to extend his joint work w ith C. Krattenthaler on enumeration of lozenge tilings of certain regions of the triangular lattice to more general (possibly weighted) regions relevant to plane partition enumeration. This research is in the general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods of studying how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.
