Applications of Graphical Condensation for Enumerating Matchings and Tilings
| dc.creator | Kuo, Eric H. | |
| dc.date | 2003-04-07 | |
| dc.date | 2003-09-11 | |
| dc.date.accessioned | 2026-07-07T04:56:41Z | |
| dc.date.available | 2026-07-07T04:56:41Z | |
| dc.description | A technique called graphical condensation is used to prove various combinatorial identities among numbers of (perfect) matchings of planar bipartite graphs and tilings of regions. Graphical condensation involves superimposing matchings of a graph onto matchings of a smaller subgraph, and then re-partitioning the united matching (actually a multigraph) into matchings of two other subgraphs, in one of two possible ways. This technique can be used to enumerate perfect matchings of a wide variety of bipartite planar graphs. Applications include domino tilings of Aztec diamonds and rectangles, diabolo tilings of fortresses, plane partitions, and transpose complement plane partitions. | |
| dc.description | 25 pages; 21 figures Corrected typos; Updated references; Some text revised, but content essentially the same | |
| dc.identifier | https://arxiv.org/abs/math/0304090 | |
| dc.identifier | http://arxiv.org/abs/math/0304090 | |
| dc.identifier | Theoretical Computer Science, Vol. 319/1-3 (2004), pp. 29-57 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67009 | |
| dc.subject | Combinatorics | |
| dc.subject | 05A15; 05C70 | |
| dc.title | Applications of Graphical Condensation for Enumerating Matchings and Tilings | |
| dc.type | text |