Enumeration of Perfect Matching of Graphs with Applications
Enumeration of Perfect Matching of Graphs with Applications
批准号:
9802390
负责人:
Mihai Ciucu
金额:
$7.71万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
1998
资助国家:
美国
项目状态:
已结题
起止时间:
1998-07-01 至 2001-06-30
中文摘要
丘库9802390 该项目关注的是某些特殊图的完美匹配的枚举,这些特殊图与组合学中的几个重要问题(生成树,平面划分,交替符号矩阵的枚举)密切相关,并且与概率(快速混合马尔可夫链)和统计物理(二聚体模型和顶点模型)中的有趣问题也有很强的联系。具体来说,基于解决方案的PI发现一个开放的生成树枚举问题所提出的斯坦利,PI打算扩展的想法,在他以前的工作的因式分解定理完美匹配的对称图,以获得类似的因式分解的特征多项式的图,因此,生成树。此外,PI打算使用他在完美匹配的互补定理方面的工作中的想法来对阿兹特克钻石的周期性加权进行分类,从而得出很好的枚举公式。这将给出一个统一的角度来看几个结果的Elkies,Kuperberg,拉森和Propp,B。Y.杨斯坦利和私家侦探除了上述核心研究计划外,PI还打算研究三个额外的问题。首先,PI将寻求将Diaconis和Saloff-Coste的比较结果扩展到不可逆马尔可夫链。这将允许一个推导出快速混合的基本移动马尔可夫链上的某些三维"菱形“平铺,认为由PI作为一个模拟的二维情况研究的吕比,兰德尔和辛克莱。第二,PI将继续他对三维二聚体问题的研究,除了考虑简单的立方晶格外,还考虑其他类似的晶格(例如,体心立方晶格或面心立方晶格),以及可能适合于这种分析的一些其它问题(例如,立方晶格的三种着色)。第三,PI打算扩大他与C的合作。Krattenthaler枚举菱形平铺的某些地区的三角形晶格更一般(可能加权)地区有关的平面分区枚举。 这项研究是在组合数学的一般领域。组合数学的目标之一是找到有效的方法来研究如何安排对象的离散集合。离散系统的行为对现代通信极为重要。例如,大型网络的设计,如电话系统中的网络设计,以及计算机科学中的算法设计,都要处理离散的对象集,这就需要使用组合研究。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Dimer systems with gaps and their connections with statistical physics, plane partitions, and alternating sign matrices
-
批准号:1501052
-
项目类别:Continuing Grant
-
资助金额:$21.0万
-
财政年份:2015
-
负责人:Mihai Ciucu
-
依托单位:
The interaction of gaps in dimer systems and beyond
-
批准号:1101670
-
项目类别:Standard Grant
-
资助金额:$17.82万
-
财政年份:2011
-
负责人:Mihai Ciucu
-
依托单位:
Dimer-mediated interaction of gaps in lattice graphs
-
批准号:0801625
-
项目类别:Continuing Grant
-
资助金额:$12.75万
-
财政年份:2008
-
负责人:Mihai Ciucu
-
依托单位:
Asymptotic Enumeration of Tilings of Lattice Regions With Holes: A Finer Analysis Under Various Boundary Conditions
-
批准号:0500616
-
项目类别:Continuing Grant
-
资助金额:$0.0万
-
财政年份:2005
-
负责人:Mihai Ciucu
-
依托单位:
Asymptotic Enumeration of Perfect Matchings of Lattice Graphs
-
批准号:0100950
-
项目类别:Continuing Grant
-
资助金额:$8.07万
-
财政年份:2001
-
负责人:Mihai Ciucu
-
依托单位:
海外基金