The Cubical Matching Complex

Richard Ehrenborg

doi:10.1007/s00026-013-0212-7

The Cubical Matching Complex

Richard Ehrenborg

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

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 f₀ - f₁ + f₂ -...= 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 language	English
Pages (from-to)	75-81
Number of pages	7
Journal	Annals of Combinatorics
Volume	18
Issue number	1
DOIs	https://doi.org/10.1007/s00026-013-0212-7
State	Published - 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.

Keywords

collapsible cubical complexes
domino tilings
lozenges tilings

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00026-013-0212-7

Cite this

@article{54f5aac0366641d2a4da9de0dff768f8,

title = "The Cubical Matching Complex",

abstract = "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.",

keywords = "collapsible cubical complexes, domino tilings, lozenges tilings",

author = "Richard Ehrenborg",

note = "Funding Information: Acknowledgments. The author would like to thank G{\'a}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.",

year = "2014",

month = mar,

doi = "10.1007/s00026-013-0212-7",

language = "English",

volume = "18",

pages = "75--81",

number = "1",

}

TY - JOUR

T1 - The Cubical Matching Complex

AU - Ehrenborg, Richard

N1 - 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.

PY - 2014/3

Y1 - 2014/3

N2 - 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.

AB - 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.

KW - collapsible cubical complexes

KW - domino tilings

KW - lozenges tilings

UR - http://www.scopus.com/inward/record.url?scp=84897580443&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84897580443&partnerID=8YFLogxK

U2 - 10.1007/s00026-013-0212-7

DO - 10.1007/s00026-013-0212-7

M3 - Article

AN - SCOPUS:84897580443

SN - 0218-0006

VL - 18

SP - 75

EP - 81

JO - Annals of Combinatorics

JF - Annals of Combinatorics

IS - 1

ER -

The Cubical Matching Complex

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this