Complexes of graphs with bounded matching size

DOI10.1007/S10801-007-0092-1zbMATH Open1161.05061arXivmath/0410345OpenAlexW1993093049MaRDI QIDQ925308FDOQ925308

Authors: Svante Linusson, John Shareshian, Volkmar Welker 

Publication date: 3 June 2008

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

Abstract: For positive integers k,n, we investigate the simplicial complex NM_k(n) of all graphs G on vertex set [n] such that every matching in G has size less than k. This complex (along with other associated cell complexes) is found to be homotopy equivalent to a wedge of spheres. The number and dimension of the spheres in the wedge are determined, and (partially conjectural) links to other combinatorially defined complexes are described. In addition we study for positive integers r,s and k the simplicial complex BNM_k(n) of all bipartite graphs G on bipartition [r] cup [�ar{s}] such that there is no matching of size k in G, and obtain results similar to those obtained for NM_k(n).

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

Recommendations

• Higher matching complexes of complete graphs and complete bipartite graphs
• Leray numbers of complexes of graphs with bounded matching number
• Topology of matching, chessboard, and general bounded degree graph complexes
• Perfect matching complexes of honeycomb graphs
• Matching complexes of small grids

zbMATH Keywords

CriticalGallai-EdmondsTrees of triangles

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Morse theory for cell complexes
• Matching theory
• The cohomology ring of the real locus of the moduli space of stable curves of genus 0 with marked points
• On Lie \(k\)-algebras
• Shellable and Cohen-Macaulay Partially Ordered Sets
• Topology of matching, chessboard, and general bounded degree graph complexes
• Discrete Morse theory for complexes of 2-connected graphs
• A topological approach to evasiveness
• Collapsibility of Δ(Π_{𝑛})/𝒮_{𝓃} and some related CW complexes
• Complexes of not \(i\)-connected graphs
• Monotone Bipartite Graph Properties are Evasive
• Simplicial Complexes of Graphs and Hypergraphs with a Bounded Covering Number
• On the topology of simplicial complexes related to 3-connected and Hamiltonian graphs
• Otter's method and the homology of homeomorphically irreducible \(k\)-trees
• Partitions into Even and Odd Block Size and Some Unusual Characters of the Symmetric Groups

Cited In (13)

• A characterization of two-dimensional Buchsbaum matching complexes
• Topology of cut complexes of graphs
• Complexes of graphs with bounded independence number
• Capacities of graphs and \(2\)-matchings
• Leray numbers of complexes of graphs with bounded matching number
• Filtered matchings and simplicial complexes
• Topology of clique complexes of line graphs
• The NF-Number of a Simplicial Complex
• Higher matching complexes of complete graphs and complete bipartite graphs
• Perfect matching complexes of honeycomb graphs
• Topology of matching, chessboard, and general bounded degree graph complexes
• The clique complex and hypergraph matching
• Matching for Graphs of Bounded Degree

This page was built for publication: Complexes of graphs with bounded matching size

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