Geodesic
Generalizing the divisibility property of rectangle domino tilings
Forest Tong1
1Massachusetts Institute of Technology
The electronic journal of combinatorics, Tome 23 (2016) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We introduce a class of graphs called compound graphs, which are constructed out of copies of a planar bipartite base graph, and explore the number of perfect matchings of compound graphs. The main result is that the number of matchings of every compound graph is divisible by the number of matchings of its base graph. Our approach is to use Kasteleyn's theorem to prove a key lemma, from which the divisibility theorem follows combinatorially. This theorem is then applied to provide a proof of Problem 21 of Propp's Enumeration of Matchings, a divisibility property of rectangles. Finally, we present a new proof, in the same spirit, of Ciucu's factorization theorem.
DOI : 10.37236/4520
Classification : 05C70, 05C76, 05B45
Mots-clés : Kasteleyn theorem, Propp's enumeration of matchings, Ciucu's factorization theorem

Forest Tong  1

1 Massachusetts Institute of Technology 
@article{10_37236_4520,
     author = {Forest Tong},
     title = {Generalizing the divisibility property of rectangle domino tilings},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {3},
     doi = {10.37236/4520},
     zbl = {1339.05326},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4520/}
}
TY  - JOUR
AU  - Forest Tong
TI  - Generalizing the divisibility property of rectangle domino tilings
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4520/
DO  - 10.37236/4520
ID  - 10_37236_4520
ER  - 
%0 Journal Article
%A Forest Tong
%T Generalizing the divisibility property of rectangle domino tilings
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4520/
%R 10.37236/4520
%F 10_37236_4520
Forest Tong. Generalizing the divisibility property of rectangle domino tilings. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/4520

Cité par Sources :