Matching complexes of trees and applications of the matching tree algorithm

DOI10.1007/S00026-022-00605-3zbMATH Open1503.05131arXiv1905.10560OpenAlexW2945133306MaRDI QIDQ2093269FDOQ2093269

Marija Jelić Milutinović, Julianne Vega, Helen Jenne, Alex McDonough

Publication date: 7 November 2022

Published in: Annals of Combinatorics (Search for Journal in Brave)

Abstract: 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 extit{Matching Tree Algorithm} to study the connectivity of honeycomb graphs, partially answering a question raised by Jonsson.

Full work available at URL: https://arxiv.org/abs/1905.10560

zbMATH Keywords

homotopy typecaterpillar graphmatching complexhoneycomb graphmatching tree algorithm

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of simplicial complexes (05E45)

Cites Work

• Title not available (Why is that?)
• Optimal decision trees on simplicial complexes
• Simplicial complexes of graphs
• Homotopy properties of the poset of nontrivial p-subgroups of a group
• Complexes of directed trees and independence complexes
• Complexes of directed trees
• Vertex decomposable graphs and obstructions to shellability
• Symmetries of plane partitions
• Homology of certain sets of 2-subgroups of symmetric groups
• On the Betti numbers of chessboard complexes
• Shellability of chessboard complexes
• Symmetries of plane partitions and the permanent-determinant method
• Topology of matching, chessboard, and general bounded degree graph complexes
• Chessboard Complexes and Matching Complexes
• Torsion in the matching complex and chessboard complex
• A user's guide to discrete Morse theory
• Star clusters in independence complexes of graphs
• Combinatorial algebraic topology
• Independence complexes of stable Kneser graphs
• Independence complexes of claw-free graphs
• On the independence complex of square grids
• The colored Tverberg's problem and complexes of injective functions
• Splittings of independence complexes and the powers of cycles
• Cores of simplicial complexes
• A uniform approach to complexes arising from forests
• Euler characteristics of discrete groups and G-spaces
• Euler characteristics of groups: The \(p\)-fractional part
• Poset fiber theorems
• MANIFOLD MATCHING COMPLEXES
• Homotopy Groups of Joins and Unions
• Bounded degree complexes of forests
• Matching complexes of trees and applications of the matching tree algorithm
• Matching complexes of small grids
• Matching and independence complexes related to small grids

Cited In (9)

• General polygonal line tilings and their matching complexes
• On the homotopy type of multipath complexes
• Title not available (Why is that?)
• An efficient algorithm for some tree matching problems
• Two Matching Based Algorithm for Tree Network Design
• Matchings on trees and the adjacency matrix: A determinantal viewpoint
• Perfect matching complexes of honeycomb graphs
• Title not available (Why is that?)
• Matching complexes of trees and applications of the matching tree algorithm

This page was built for publication: Matching complexes of trees and applications of the matching tree algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2093269)