Enumeration of Perfect Matching of Graphs with Applications

Cucu 9802390这个项目涉及某些特殊图的完美匹配的计数，这些图被证明与组合学中的几个重要问题(生成树的计数、平面划分、交替符号矩阵)密切相关，也与概率(快速混合马尔可夫链)和统计物理(二聚体模型和顶点模型)中的有趣问题有很强的联系。具体地说，基于Pi对Stanley提出的一个开生成树计数问题的解，PI打算推广他以前关于对称图的完美匹配的因式分解定理的思想，以得到图的特征多项式的相似因式分解，并由此得到生成树的类似因式分解。此外，PI打算使用他在完美匹配的互补定理方面的工作的想法来对阿兹特克钻石的周期性加权进行分类，从而得到良好的计数公式。这将给Elkies，Kuperberg，Larsen和Propp，B.Y.Yang，Stanley和PI的几个结果提供一个统一的视角。除了上面概述的核心研究计划外，PI还打算解决另外三个问题。首先，PI将把Diaconis和Saloff-Coste的比较结果推广到不可逆马氏链。这将使人们能够推断出基本移动马尔科夫链在某些三维的“菱形”瓷砖上的快速混合，PI认为这是卢比、兰德尔和辛克莱研究的二维情况的模拟。其次，PI将继续他对三维二聚体问题的研究，除了简单的立方晶格之外，还将考虑其他感兴趣的晶格(例如，体心立方晶格或面心立方晶格)，以及一些可能适合于这种分析的其他问题(例如，立方晶格的三色)。第三，PI打算将他与C.Krtenthaler关于三角格子某些区域的菱形瓦片的计数的合作工作扩展到与平面划分计数相关的更一般(可能是加权的)区域。这项研究属于组合学的一般领域。组合学的目标之一是找到有效的方法来研究离散的对象集合如何排列。离散系统的行为对于现代通信来说是极其重要的。例如，大型网络的设计，如那些发生在电话系统中的网络，以及计算机科学中的算法设计，都涉及离散的对象集，这利用了组合研究。

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.