A complementation theorem for perfect matchings of graphs having a cellular completion

被引：34

作者：

Ciucu, M ^{[1
]}

机构：

[1] Inst Adv Study, Sch Math, Princeton, NJ 08540 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES A | 1998年 / 81卷 / 01期

关键词：

D O I：

10.1006/jcta.1997.2799

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A cellular graph is a graph whose edges can be partitioned into 4-cycles (called cells) so that each vertex is contained in at most two cells. We present a "Complementation Theorem" for the number of matchings of certain subgraphs of cellular graphs. This generalizes the main result of M. Ciucu (J. Algebraic Combin. 5(1996), 87-103). As applications of the Complementation Theorem wi obtain a new proof of Stanley's multivariate version of the Aztec diamond theorem, a weighted generalization of a result of Knuth (J. Algebraic Combin. 6 (1997), 253-257) concerning spanning trees of Aztec diamond graphs, a combinatorial proof of Yang's enumeration ("Three Enumeration Problems Concerning Aztec Diamonds," Ph.D. thesis, M.L.T., 1991) of matchings of fortress graphs and direct proofs for certain identities of Jokusch and Propp. (C) 1998 Academic Press.

引用

页码：34 / 68

页数：35

共 19 条

[1]

CHOW T, Q SPECTRUM SPANNING

[2] Perfect matchings of cellular graphs [J].

Ciucu, M .

JOURNAL OF ALGEBRAIC COMBINATORICS, 1996, 5 (02) :87-103

[3]

CIUCU M, IN PRESS J COMBIN A

[4]

CIUCU M, 1996, THEIS SU MICHIGAN AN

[5]

ELKIES N, 1992, J ALGEBR COMB, V1, P219

[6]

Elkies N., 1992, J. Algebraic Combin., V1, P111, DOI [10.1023/A:1022420103267, DOI 10.1023/A:1022420103267]

[7]

JOCKUSCH W, ANTISYMMETRIC MONOTO

[8] Aztec diamonds, checkerboard graphs, and spanning trees [J].

Knuth, DE .

JOURNAL OF ALGEBRAIC COMBINATORICS, 1997, 6 (03) :253-257

[9]

Kuperberg G, 1996, INT MATH RES NOTICES, V3, P139, DOI DOI 10.1155/S1073792896000128

[10]

KUPERBRG G, COMMNICATION

← 1 2 →