For positive integers
k,
n, we investigate the simplicial complex
NMk(n)\mathsf{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
BNMk(r,s)\mathsf{BNM}_{k}(r,s)
of all bipartite graphs
G on bipartition
[r]È[[`(s)]][r]\cup [\bar{s}]
such that there is no matching of size
k in
G, and obtain results similar to those obtained for
NMk(n)\mathsf{NM}_{k}(n)
.
Keywords Critical - Trees of triangles - Gallai-Edmonds
S. Linusson and V. Welker supported by EC’s IHRP program through grant HPRN-CT-2001-00272. J. Shareshian partially supported
by National Science Foundation grants DMS-0070757 and DMS-0030483.