The Cubical Matching Complex

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Given a bipartite planar graph embedded in the plane, we define its cubical matching complex. By combining results of Kalai and Propp, we show that the cubical matching complex is collapsible. As a corollary, we obtain that a simply connected region R in the plane that can be tiled with lozenges and hexagons satisfies f0 - f1 + f2 -...= 1, where f i is the number of tilings with i hexagons. The same relation holds for a region tiled with dominoes and 2 × 2 squares. Furthermore, we show for a region that can be tiled with dominoes, that each link of the associated cubical complex C(R) is either collapsible or homotopy equivalent to a sphere.

Original languageEnglish
Pages (from-to)75-81
Number of pages7
JournalAnnals of Combinatorics
Issue number1
StatePublished - Mar 2014

Bibliographical note

Funding Information:
Acknowledgments. The author would like to thank Gábor Hetyei and Margaret Readdy for helpful discussions and the Institute for Advanced Study where this research was carried out. Furthermore, the author thanks the referee for comments clarifying the exposition. The author was partially supported by National Science Foundation grants DMS-0902063, DMS-0835373 and CCF-0832797.


  • collapsible cubical complexes
  • domino tilings
  • lozenges tilings

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'The Cubical Matching Complex'. Together they form a unique fingerprint.

Cite this