Two Decompositions in Topological Combinatorics with Applications to Matroid Complexes

Chari, Manoj

doi:10.1090/S0002-9947-97-01921-1

Two Decompositions in Topological Combinatorics with Applications to Matroid Complexes
HTML articles powered by AMS MathViewer

by Manoj K. Chari PDF

Trans. Amer. Math. Soc. 349 (1997), 3925-3943 Request permission

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 [Face numbers inequalities for matroid complexes and Cohen-Macaulay types of Stanley-Reisner rings of distributive lattices, Pacific Journal of Math. 154 (1992), 253-264] that the $h$-vector of a matroid complex satisfies the above two sets of inequalities.

References

Ian Anderson, Combinatorics of finite sets, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1987. MR 892525
L. J. Billera, Polyhedral theory and commutative algebra, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin-New York, 1983, pp. 57–77. MR 717396
Anders Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), no. 1, 159–183. MR 570784, DOI 10.1090/S0002-9947-1980-0570784-2
Anders Björner, The homology and shellability of matroids and geometric lattices, Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 226–283. MR 1165544, DOI 10.1017/CBO9780511662041.008
Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler, Oriented matroids, Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1993. MR 1226888
A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872. MR 1373690
Jason I. Brown and Charles J. Colbourn, Roots of the reliability polynomial, SIAM J. Discrete Math. 5 (1992), no. 4, 571–585. MR 1186825, DOI 10.1137/0405047
H. Bruggesser and P. Mani, Shellable decompositions of cells and spheres, Math. Scand. 29 (1971), 197–205 (1972). MR 328944, DOI 10.7146/math.scand.a-11045
Tom Brylawski, The broken-circuit complex, Trans. Amer. Math. Soc. 234 (1977), no. 2, 417–433. MR 468931, DOI 10.1090/S0002-9947-1977-0468931-6
Manoj K. Chari, Matroid inequalities, Discrete Math. 147 (1995), no. 1-3, 283–286. MR 1364520, DOI 10.1016/0012-365X(95)00122-D
Charles J. Colbourn, Some open problems on reliability polynomials, Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993), 1993, pp. 187–202. MR 1267249
Raul Cordovil, On simplicial matroids and Sperner’s lemma, Matroid theory (Szeged, 1982) Colloq. Math. Soc. János Bolyai, vol. 40, North-Holland, Amsterdam, 1985, pp. 97–105. MR 843373
Jeremy E. Dawson, A collection of sets related to the Tutte polynomial of a matroid, Graph theory, Singapore 1983, Lecture Notes in Math., vol. 1073, Springer, Berlin, 1984, pp. 193–204. MR 761018, DOI 10.1007/BFb0073117
Gopal Danaraj and Victor Klee, Shellings of spheres and polytopes, Duke Math. J. 41 (1974), 443–451. MR 345113
Barry H. Dayton and Charles A. Weibel, $K$-theory of hyperplanes, Trans. Amer. Math. Soc. 257 (1980), no. 1, 119–141. MR 549158, DOI 10.1090/S0002-9947-1980-0549158-6
Takayuki Hibi, What can be said about pure $O$-sequences?, J. Combin. Theory Ser. A 50 (1989), no. 2, 319–322. MR 989204, DOI 10.1016/0097-3165(89)90025-3
Takayuki Hibi, Face number inequalities for matroid complexes and Cohen-Macaulay types of Stanley-Reisner rings of distributive lattices, Pacific J. Math. 154 (1992), no. 2, 253–264. MR 1159510, DOI 10.2140/pjm.1992.154.253
Gil Kalai, The diameter of graphs of convex polytopes and $f$-vector theory, Applied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, Amer. Math. Soc., Providence, RI, 1991, pp. 387–411. MR 1116365, DOI 10.1016/0899-8256(91)90037-F
L. Lovász and M. D. Plummer, Matching theory, North-Holland Mathematics Studies, vol. 121, North-Holland Publishing Co., Amsterdam; North-Holland Publishing Co., Amsterdam, 1986. Annals of Discrete Mathematics, 29. MR 859549
James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179–184. MR 283691, DOI 10.1112/S0025579300002850
P. McMullen, The numbers of faces of simplicial polytopes, Israel J. Math. 9 (1971), 559–570. MR 278183, DOI 10.1007/BF02771471
Peter McMullen, On simple polytopes, Invent. Math. 113 (1993), no. 2, 419–444. MR 1228132, DOI 10.1007/BF01244313
James G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1207587
J. Scott Provan and Louis J. Billera, Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res. 5 (1980), no. 4, 576–594. MR 593648, DOI 10.1287/moor.5.4.576
Richard P. Stanley, Cohen-Macaulay complexes, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht, 1977, pp. 51–62. MR 0572989
Richard P. Stanley, The number of faces of a simplicial convex polytope, Adv. in Math. 35 (1980), no. 3, 236–238. MR 563925, DOI 10.1016/0001-8708(80)90050-X
Richard P. Stanley, Combinatorics and commutative algebra, Progress in Mathematics, vol. 41, Birkhäuser Boston, Inc., Boston, MA, 1983. MR 725505, DOI 10.1007/978-1-4899-6752-7
Richard P. Stanley, Enumerative combinatorics. Vol. I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986. With a foreword by Gian-Carlo Rota. MR 847717, DOI 10.1007/978-1-4615-9763-6
Richard P. Stanley, A monotonicity property of $h$-vectors and $h^*$-vectors, European J. Combin. 14 (1993), no. 3, 251–258. MR 1215335, DOI 10.1006/eujc.1993.1028
Richard P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Graph theory and its applications: East and West (Jinan, 1986) Ann. New York Acad. Sci., vol. 576, New York Acad. Sci., New York, 1989, pp. 500–535. MR 1110850, DOI 10.1111/j.1749-6632.1989.tb16434.x
D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0427112
Günter M. Ziegler, Matroid shellability, $\beta$-systems, and affine hyperplane arrangements, J. Algebraic Combin. 1 (1992), no. 3, 283–300. MR 1194080, DOI 10.1023/A:1022492019120
Tudor Zamfirescu, Points joined by three shortest paths on convex surfaces, Proc. Amer. Math. Soc. 123 (1995), no. 11, 3513–3518. MR 1273530, DOI 10.1090/S0002-9939-1995-1273530-9