Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Two Decompositions in Topological Combinatorics with Applications to Matroid Complexes


Author: Manoj K. Chari
Journal: Trans. Amer. Math. Soc. 349 (1997), 3925-3943
MSC (1991): Primary 52B40; Secondary 06A07
DOI: https://doi.org/10.1090/S0002-9947-97-01921-1
MathSciNet review: 1422892
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper introduces two new decomposition techniques which are related to the classical notion of shellability of simplicial complexes, and uses the existence of these decompositions to deduce certain numerical properties for an associated enumerative invariant. First, we introduce the notion of M-shellability, which is a generalization to pure posets of the property of shellability of simplicial complexes, and derive inequalities that the rank-numbers of M-shellable posets must satisfy. We also introduce a decomposition property for simplicial complexes called a convex ear-decomposition, and, using results of Kalai and Stanley on $h$-vectors of simplicial polytopes, we show that $h$-vectors of pure rank-$d$ simplicial complexes that have this property satisfy $h_{0} \leq h_{1} \leq \cdots \leq h_{[d/2]}$ and $h_{i} \leq h_{d-i}$ for $ 0 \leq i \leq [d/2]$. We then show that the abstract simplicial complex formed by the collection of independent sets of a matroid (or matroid complex) admits a special type of convex ear-decomposition called a PS ear-decomposition. This enables us to construct an associated M-shellable poset, whose set of rank-numbers is the $h$-vector of the matroid complex. This results in a combinatorial proof of a conjecture of Hibi that the $h$-vector of a matroid complex satisfies the above two sets of inequalities.


References [Enhancements On Off] (What's this?)

  • 1. I. Anderson (1987). Combinatorics of Finite Sets, Oxford Science Publications, Oxford University Press. MR 89b:05001
  • 2. L. J. Billera (1984). Polyhedral Combinatorics and Commutative Algebra, in Mathematical Programming: The State of the Art, (A. Bachem, B. Korte, Eds.), Springer-Verlag, 57-77. MR 84m:52009
  • 3. A. Björner (1980). Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260, 159-183. MR 81i:06001
  • 4. A. Björner (1992). Homology and Shellability of Matroids and Geometric Lattices, in Matroid Applications, (N. White, Ed.), Encyclopaedia of Mathematics and its Applications, Cambridge University Press, 226-283. MR 94a:52030
  • 5. A. Björner, M. Las Vergnas, B. Sturmfels, N. White, G. Ziegler (1992). Oriented Matroids, Cambridge University Press, Cambridge. MR 95e:52023
  • 6. A. Björner (1996). Topological Methods, in Handbook of Combinatorics, Vol. II, (R. Graham,
    M. Grötschel and L. Lova\'{s}z, Eds.), North-Holland, Amsterdam, pp. 1819-1872. MR 96m:52012
  • 7. J.I. Brown and C.J. Colbourn (1992). Roots of the reliability polynomial, SIAM J. of Discrete Math. 5, 571-585. MR 93g:68005
  • 8. H. Bruggesser and P. Mani (1971). Shellable decompositions of cells and spheres, Math. Scand. 29, 197-205. MR 48:7286
  • 9. T.H. Brylawski (1977). The broken-circuit complex, Trans. Amer. Math. Soc. 234, 417-433. MR 80a:05055
  • 10. M.K. Chari (1995). Matroid inequalities, Discrete Math. 147, 283-286. MR 96j:05031
  • 11. C. J. Colbourn (1993). Some open problems on reliability polynomials, DIMACS Technical Report no. 93-28, Congr. Numer. 93 (1993), 187-202. MR 95c:05121
  • 12. R. Cordovil (1985). On simplicial matroids and Sperner's Lemma, in Matroid Theory and its Applications, L. Lovasz & A. Recski (Eds), Colloq. Math. Soc. Janos Bolyai, 40 North Holland, Amsterdam and Budapest, 97-105. MR 87g:05065
  • 13. J. E. Dawson (1984). A collection of sets related to the Tutte polynomial of a matroid, in Lecture Notes in Mathematics. 1073, Springer Verlag, Berlin, 193-204. MR 85k:05032
  • 14. G. Danaraj and V. Klee (1974). Shellings of spheres and polytopes, Duke Math. J. 41, 443-451. MR 49:9852
  • 15. B.H. Dayton and C.A. Weibel (1980). K-theory of Hyperplanes, Trans. Amer. Math. Soc. 257, 119-141. MR 81e:18015
  • 16. T. Hibi (1989). What can be said about pure O-sequences?, Journal of Comb. Theory, Ser A. 50, 319-322. MR 90d:52012
  • 17. T. Hibi (1992). Face numbers inequalities for matroid complexes and Cohen-Macaulay types of Stanley-Reisner rings of distributive lattices, Pacific Journal of Math. 154, 253-264. MR 93e:52027
  • 18. G. Kalai (1991). The Diameter of Graphs of Convex Polytopes and f-Vector Theory,
    DIMACS Series in Discrete Mathematics and Theoretical Computer Science 4, 387-411. MR 92h:52010
  • 19. L. Lovasz and M.D. Plummer (1986). Matching Theory, Elsevier Science Pub. Co., New York. MR 88b:90087
  • 20. J. R. Munkres (1984). Elements of Algebraic Topology, Addison-Wesley, Menlo Park. MR 85m:55001
  • 21. P. McMullen (1970). The maximum number of faces of a convex polytope, Mathematika 17, 179-184. MR 44:921
  • 22. P. McMullen (1971). The number of faces of simplicial polytopes,Israel J. Math. 9, 559-570. MR 43:3914
  • 23. P. McMullen (1993). On Simple Polytopes, Inventiones Math. 113, 419-444. MR 94d:52015
  • 24. J.G. Oxley (1992). Matroid Theory, Oxford University Press. MR 94d:05033
  • 25. J.S. Provan and L.J. Billera (1980). Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. of O.R. 5, 579-594. MR 82c:52010
  • 26. R.P. Stanley (1977). Cohen-Macaulay complexes, in Higher Combinatorics, M.Aigner (Ed.), Reidel, Dordrecht, 384-393. MR 58:28010
  • 27. R. P Stanley (1980). The number of faces of simplicial convex polytopes, Adv. in Math. 35, 236-238. MR 81f:52014
  • 28. R P. Stanley (1996). Combinatorics and Commutative Algebra, 2nd Edition, Progress in Mathematics, Vol. 41, Birkhäuser, Boston-Basel-Stuttgart. MR 85b:05002 (1st ed.)
  • 29. R.P. Stanley (1986). Enumerative Combinatorics, Vol. I., Wadsworth-Brooks/Cole. MR 87j:05003
  • 30. R.P. Stanley (1993). A monotonicity property of $h$-vectors and $h^*$-vectors, Europ. J. Combin. 14, 251-258. MR 94f:52016
  • 31. R.P. Stanley (1989). Log-Concave and Unimodal Sequences in Algebra, Combinatorics and Geometry, Annals of the New York Academy of Sciences. 576, 500- 535. MR 92e:05124
  • 32. D.J.A Welsh (1976). Matroid Theory, Academic Press, London. MR 55:148
  • 33. G.M.Ziegler (1992), Matroid shellability, $\beta $-systems, and affine hyperplane arrangements. Journal of Algebraic Combinatorics 1, 283-300. MR 93j:52022
  • 34. G.M. Ziegler (1995), Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer Verlag, New York. MR 96a:52001

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 52B40, 06A07

Retrieve articles in all journals with MSC (1991): 52B40, 06A07


Additional Information

Manoj K. Chari
Affiliation: Department of Mathematics Louisiana State University Baton Rouge, Louisiana 70803
Email: chari@math.lsu.edu

DOI: https://doi.org/10.1090/S0002-9947-97-01921-1
Keywords: Matroid complex, shellability, simplicial complex, boundary complex, simplicial polytope, $h$-vector
Received by editor(s): May 6, 1995
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society