Bounded degree complexes of forests

DOI10.1016/J.DISC.2020.112009MaRDI QIDQ785805zbMATH OpenOpenAlexFDO

Authors Anurag Singh

Publication date 12 August 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

matching complexescaterpillar graphsbounded degree complexes

Mathematics Subject Classification ID

Combinatorial aspects of simplicial complexes (05E45) Homotopy groups of special spaces (55Q52) Algebraic topology on manifolds and differential topology (57R19)

Abstract: Given an arbitrary sequence of non-negative integers $veclambda=(lambd{a}_1,dots,lambd{a}_n)$ and a graph $G$ with vertex set $v_1,dots,v_n$, the bounded degree complex, denoted $ext{BD}^{veclambda}(G)$, is a simplicial complex whose faces are the subsets $HsubseteqE(G)$ such that for each $iin1,dots,n$, the degree of vertex $v_i$ in the induced subgraph $G[H]$ is at most $lambd{a}_i$. When $lambd{a}_i=k$ for all $i$, the bounded degree complex $ext{BD}^{veclambda}(G)$ is called the $k$-matching complex, denoted $M_k(G)$. In this article, we determine the homotopy type of bounded degree complexes of forests. In particular, we show that, for all $kgeq1$, the $k$-matching complexes of caterpillar graphs are either contractible or homotopy equivalent to a wedge of spheres, thereby proving a conjecture of Julianne Vega cite[Conjecture 7.3]{Vega19}. We also give a closed form formula for the homotopy type of the bounded degree complexes of those caterpillar graphs in which every non-leaf vertex is adjacent to at least one leaf vertex.

Recommendations

• Matching complexes of trees and applications of the matching tree algorithm
• Complexes of graphs with bounded matching size
• Topology of matching, chessboard, and general bounded degree graph complexes
• A uniform approach to complexes arising from forests
• Higher matching complexes of complete graphs and complete bipartite graphs

Cites work

• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• A uniform approach to complexes arising from forests
• Combinatorial algebraic topology
• Complexes of directed trees
• Homology of certain sets of 2-subgroups of symmetric groups
• Minimal resolutions and the homology of matching and chessboard complexes
• Shellability of chessboard complexes
• Simplicial complexes of graphs
• The homology of ``\(k\)-equal manifolds and related partition lattices
• Topology of matching, chessboard, and general bounded degree graph complexes
• Torsion in the matching complex and chessboard complex

Cited in

(7)

• scientific article; zbMATH DE number 1222606 (Why is no real title available?)
• Matching complexes, bounded degree graph complexes, and weight spaces of \(\mathrm{GL}_n\)-complexes
• Vertex decomposability of complexes associated to forests
• Higher matching complexes of complete graphs and complete bipartite graphs
• Dense forests and Danzer sets
• The graph minor theorem in topological combinatorics
• Matching complexes of trees and applications of the matching tree algorithm

This page was built for publication: Bounded degree complexes of forests

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