Complexes of Graphs with Bounded Matching Size
Svante Linusson1
, John Shareshian2
and Volkmar Welker3
1Royal Institute of Technology (KTH) Department of Mathematics 100 44 Stockholm Sweden
2Washington University Department of Mathematics St Louis MO 63130 USA
3Philipps-Universität Marburg Fachbereich Mathematik und Informatik 35032 Marburg Germany
2Washington University Department of Mathematics St Louis MO 63130 USA
3Philipps-Universität Marburg Fachbereich Mathematik und Informatik 35032 Marburg Germany
DOI: 10.1007/s10801-007-0092-1
Abstract
For positive integers k, n, we investigate the simplicial complex NM k( 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 BNM k( 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 NM k( n) \mathsf{NM}_{k}(n) .
Pages: 331–349
Keywords: keywords critical; trees of triangles; gallai-edmonds
Full Text: PDF
References
1. Babson, E., Björner, A., Linusson, S., Shareshian, J., Welker, V.: Complexes of not i-connected graphs. Topology 38, 271-299 (1999)
2. Björner, A.: Shellable and Cohen-Macaulay partially ordered sets. Trans. Am. Math. Soc. 260, 159- 183 (1980)
3. Calderbank, A.R., Hanlon, P., Robinson, R.W.: Partitions into even and odd block size and some unusual characters of the symmetric groups. Proc. Lond. Math. Soc. (3) 53, 288-320 (1986)
4. Etingof, P., Henriques, A., Kamnitzer, J., Rains, E.: The cohomology ring of the real locus of the moduli space of stable curves of genus g with marked points. Preprint, arXiv:math/0507514v2
5. Forman, R.: Morse theory for cell complexes. Adv. Math. 134, 90-145 (1998)
6. Hanlon, P.: Otter's method and the homology of homeomorphically irreducible k-trees. J. Comb. Theory Ser. A 74, 301-320 (1996)
7. Hanlon, P., Wachs, M.: On Lie k-algebras. Adv. Math. 113, 206-236 (1995)
8. Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)
9. Jonsson, J.: On the topology of simplicial complexes related to 3-connected and Hamiltonian graphs. J. Comb. Theory Ser. A 104(1), 169-199 (2003)
10. Jonsson, J.: Simplicial Complexes of Graphs. Lecture Notes in Mathematics. Springer, Heidelberg, to appear; extended version of PhD thesis, KTH, Stockholm (2005), http://www.math.kth.se/~jakobj/ thesis.html
11. Kahn, J., Saks, M., Sturtevant, D.: A topological approach to evasiveness. Combinatorica 4, 297-306 (1984)
12. Kozlov, D.N.: Collapsibility of ( n)/Sn and some related CW complexes. Proc. Am. Math. Soc. 128, 2253-2259 (2000)
13. Lovász, L., Plummer, M.D.: Matching Theory. Akadémiai Kiadó, Budapest (1986)
14. Shareshian, J.: Discrete Morse theory for complexes of 2-connected graphs. Topology 40, 681-701 (2001)
15. Wachs, M.L.: Topology of matching, chessboard and general bounded degree graph complexes. Alg.
2. Björner, A.: Shellable and Cohen-Macaulay partially ordered sets. Trans. Am. Math. Soc. 260, 159- 183 (1980)
3. Calderbank, A.R., Hanlon, P., Robinson, R.W.: Partitions into even and odd block size and some unusual characters of the symmetric groups. Proc. Lond. Math. Soc. (3) 53, 288-320 (1986)
4. Etingof, P., Henriques, A., Kamnitzer, J., Rains, E.: The cohomology ring of the real locus of the moduli space of stable curves of genus g with marked points. Preprint, arXiv:math/0507514v2
5. Forman, R.: Morse theory for cell complexes. Adv. Math. 134, 90-145 (1998)
6. Hanlon, P.: Otter's method and the homology of homeomorphically irreducible k-trees. J. Comb. Theory Ser. A 74, 301-320 (1996)
7. Hanlon, P., Wachs, M.: On Lie k-algebras. Adv. Math. 113, 206-236 (1995)
8. Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)
9. Jonsson, J.: On the topology of simplicial complexes related to 3-connected and Hamiltonian graphs. J. Comb. Theory Ser. A 104(1), 169-199 (2003)
10. Jonsson, J.: Simplicial Complexes of Graphs. Lecture Notes in Mathematics. Springer, Heidelberg, to appear; extended version of PhD thesis, KTH, Stockholm (2005), http://www.math.kth.se/~jakobj/ thesis.html
11. Kahn, J., Saks, M., Sturtevant, D.: A topological approach to evasiveness. Combinatorica 4, 297-306 (1984)
12. Kozlov, D.N.: Collapsibility of ( n)/Sn and some related CW complexes. Proc. Am. Math. Soc. 128, 2253-2259 (2000)
13. Lovász, L., Plummer, M.D.: Matching Theory. Akadémiai Kiadó, Budapest (1986)
14. Shareshian, J.: Discrete Morse theory for complexes of 2-connected graphs. Topology 40, 681-701 (2001)
15. Wachs, M.L.: Topology of matching, chessboard and general bounded degree graph complexes. Alg.