Matching Complexes of Trees and Applications of the Matching Tree Algorithm

A matching complex of a simple graph G is a simplicial complex with faces given by the matchings of G . The topology of matching complexes is mysterious; there are few graphs for which the homotopy type is known. Marietti and Testa showed that matching complexes of forests are contractible or homoto...

Full description

Saved in:
Bibliographic Details
Published in:Annals of combinatorics 2022-12, Vol.26 (4), p.1041-1075
Main Authors: Jelić Milutinović, Marija, Jenne, Helen, McDonough, Alex, Vega, Julianne
Format: Article
Language:English
Subjects:
Algorithms
caterpillar graph
Combinatorics
Graph theory
Graphs
homotopy type
honeycomb graph
Matching
matching complex
matching tree algorithm
Mathematics
MATHEMATICS AND COMPUTING
Mathematics and Statistics
Topology
Trees (mathematics)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A matching complex of a simple graph G is a simplicial complex with faces given by the matchings of G . The topology of matching complexes is mysterious; there are few graphs for which the homotopy type is known. Marietti and Testa showed that matching complexes of forests are contractible or homotopy equivalent to a wedge of spheres. We study two specific families of trees. For caterpillar graphs, we give explicit formulas for the number of spheres in each dimension and for perfect binary trees we find a strict connectivity bound. We also use a tool from discrete Morse theory called the Matching Tree Algorithm to study the connectivity of honeycomb graphs, partially answering a question raised by Jonsson.
ISSN:0218-0006
0219-3094
DOI:10.1007/s00026-022-00605-3