Complexes of graphs with bounded matching size

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

Authors Svante Linusson, John Shareshian, Volkmar Welker

Publication date 3 June 2008

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

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

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)

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).

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

Cites work

• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• A topological approach to evasiveness
• Collapsibility of Δ(Π_{𝑛})/𝒮_{𝓃} and some related CW complexes
• Complexes of not \(i\)-connected graphs
• Discrete Morse theory for complexes of 2-connected graphs
• Matching theory
• Monotone Bipartite Graph Properties are Evasive
• Morse theory for cell complexes
• On Lie \(k\)-algebras
• 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
• Shellable and Cohen-Macaulay Partially Ordered Sets
• Simplicial Complexes of Graphs and Hypergraphs with a Bounded Covering Number
• The cohomology ring of the real locus of the moduli space of stable curves of genus 0 with marked points
• Topology of matching, chessboard, and general bounded degree graph complexes

Cited in

(17)

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

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)