Complexes of Graphs with Bounded Matching Size

by: Svante Linusson, John Shareshian, Volkmar Welker

Journal of Algebraic Combinatorics, Vol. 27, No. 3. (10 May 2008), pp. 331-349.

View FullText article

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

AbnerCYH

Find related articles with these CiteULike tags

algebra, graph, topology

Abstract

Abstract For positive integers k,n, we investigate the simplicial complex 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 of all bipartite graphs G on bipartition such that there is no matching of size k in G, and obtain results similar to those obtained for .

@article{citeulike:2667165, abstract = {Abstract\ \  For positive integers k,n, we investigate the simplicial complex 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 of all bipartite graphs G on bipartition such that there is no matching of size k in G, and obtain results similar to those obtained for .}, author = {Linusson, Svante and Shareshian, John and Welker, Volkmar }, citeulike-article-id = {2667165}, doi = {10.1007/s10801-007-0092-1}, journal = {Journal of Algebraic Combinatorics}, keywords = {algebra, graph, topology}, month = {May}, number = {3}, pages = {331--349}, posted-at = {2008-04-14 11:00:37}, priority = {2}, title = {Complexes of Graphs with Bounded Matching Size}, url = {http://dx.doi.org/10.1007/s10801-007-0092-1}, volume = {27}, year = {2008} }

RIS record

TY - JOUR ID - citeulike:2667165 L3 - citeulike-article-id:2667165 TI - Complexes of Graphs with Bounded Matching Size JF - Journal of Algebraic Combinatorics VL - 27 IS - 3 SP - 331 EP - 349 N2 - Abstract   For positive integers k,n, we investigate the simplicial complex 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 of all bipartite graphs G on bipartition such that there is no matching of size k in G, and obtain results similar to those obtained for . KW - algebra KW - graph KW - topology AU - Linusson, Svante AU - Shareshian, John AU - Welker, Volkmar PY - 2008/05/10/ UR - http://dx.doi.org/10.1007/s10801-007-0092-1 ER -

RIS BibTeX