Matching and independence complexes related to small grids

Benjamin Braun; Wesley K. Hough

doi:10.37236/6212

Matching and independence complexes related to small grids

Benjamin Braun, Wesley K. Hough

Mathematics

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

10 Scopus citations

Abstract

The topology of the matching complex for the 2×n grid graph is mysterious. We describe a discrete Morse matching for a family of independence complexes Ind(Δ^m _n) that include these matching complexes. Using this matching, we determine the dimensions of the chain spaces for the resulting Morse complexes and derive bounds on the location of non-trivial homology groups for certain Ind(Δ^m _n). Furthermore, we determine the Euler characteristic of Ind(Δ^m _n) and prove that several homology groups of Ind(Δ^m _n) are non-zero.

Original language	English
Article number	#P4.18
Journal	Electronic Journal of Combinatorics
Volume	24
Issue number	4
DOIs	https://doi.org/10.37236/6212
State	Published - Oct 20 2017

Bibliographical note

Publisher Copyright:
© 2017, Australian National University. All rights reserved.

Funding

Partially supported by grant H98230-16-1-0045 from the U.S. National Security Agency. ∗Partially supported by grant H98230-16-1-0045 from the U.S. National Security Agency.

Funders	Funder number
U.S. National Security Agency
National Security Agency	H98230-16-1-0045

Keywords

Grid graphs
Homology
Independence complexes
Recursions

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/6212

Cite this

@article{9b78b7bd0a52468cbcb3ebe5f54f01c9,

title = "Matching and independence complexes related to small grids",

abstract = "The topology of the matching complex for the 2×n grid graph is mysterious. We describe a discrete Morse matching for a family of independence complexes Ind(Δm n) that include these matching complexes. Using this matching, we determine the dimensions of the chain spaces for the resulting Morse complexes and derive bounds on the location of non-trivial homology groups for certain Ind(Δm n). Furthermore, we determine the Euler characteristic of Ind(Δm n) and prove that several homology groups of Ind(Δm n) are non-zero.",

keywords = "Grid graphs, Homology, Independence complexes, Recursions",

author = "Benjamin Braun and \{K. Hough\}, Wesley",

year = "2017",

month = oct,

day = "20",

doi = "10.37236/6212",

language = "English",

volume = "24",

number = "4",

}

TY - JOUR

T1 - Matching and independence complexes related to small grids

AU - Braun, Benjamin

AU - K. Hough, Wesley

PY - 2017/10/20

Y1 - 2017/10/20

N2 - The topology of the matching complex for the 2×n grid graph is mysterious. We describe a discrete Morse matching for a family of independence complexes Ind(Δm n) that include these matching complexes. Using this matching, we determine the dimensions of the chain spaces for the resulting Morse complexes and derive bounds on the location of non-trivial homology groups for certain Ind(Δm n). Furthermore, we determine the Euler characteristic of Ind(Δm n) and prove that several homology groups of Ind(Δm n) are non-zero.

AB - The topology of the matching complex for the 2×n grid graph is mysterious. We describe a discrete Morse matching for a family of independence complexes Ind(Δm n) that include these matching complexes. Using this matching, we determine the dimensions of the chain spaces for the resulting Morse complexes and derive bounds on the location of non-trivial homology groups for certain Ind(Δm n). Furthermore, we determine the Euler characteristic of Ind(Δm n) and prove that several homology groups of Ind(Δm n) are non-zero.

KW - Grid graphs

KW - Homology

KW - Independence complexes

KW - Recursions

UR - https://www.scopus.com/pages/publications/85035326553

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

U2 - 10.37236/6212

DO - 10.37236/6212

M3 - Article

AN - SCOPUS:85035326553

SN - 1077-8926

VL - 24

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 4

M1 - #P4.18

ER -

Matching and independence complexes related to small grids

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this