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.

Funding

Acknowledgments. The author would like to thank G\u00E1bor 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.

Funders	Funder number
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China	CCF-0832797, 0902063, DMS-0902063, DMS-0835373

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 - https://www.scopus.com/pages/publications/84897580443

UR - https://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

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this