Enumeration of the faces of complexes and normalizations of distributive lattices

A. O. Matveev

Diskretnaya Matematika, Tome 12 (2000) no. 3, pp. 76-94.

Résumé

For an arbitrary face system $\Phi\subseteq 2^{[m]}$ of the power set of the set $[m]=\{1,\dots,m\}$, we consider the vector descriptions $f(\Phi;m),h(\Phi;m)\in Q^{m+1}$ and the generating functions $$ F_{\Phi;m}(y-1)=\sum_{l=0}^mf_l(\Phi;m)(y-1)^{m-l} = H_{\Phi;m}(y)=\sum_{l=0}^mh_{l}(\Phi;m)y^{m-l}, $$ where $f_l(\Phi;m)=|\{A\in\Phi\colon |A|=l\}|$, $0\leq l\leq m$. The corresponding valuations on the Boolean lattice of all subsets of the power set $2^{[m]}$ are defined. For a partition of a face system $\Phi\subseteq{2}^{[m]}$ into Boolean intervals such that the partition consists of $p_{i,j}$ intervals $[A,B]$ with $|A|=j$ and $|B-A|=i$, $$ h_l(\Phi;m)=(-1)^l\sum_{i=0}^{m-l}\sum_{j=0}^l (-1)^j p_{i,j} \binom{m-i-j}{l-j}. $$ For a pair of mutually dual face systems $\Phi,\Phi^*\subseteq2^{[m]}$, where $\Phi^*=\{[m]-A\colon A\in{2}^{[m]}, A\notin\Phi\}$, $$ h_l(\Phi;m)+(-1)^l\sum_{j=l}^m \binom jlh_j(\Phi^*;m)=0, \qquad 1\leq l\leq m. $$

Bibliographie

[1] Riordan Dzh., Kombinatornye tozhdestva, 1982, Nauka, Moskva | MR | Zbl

[2] Billera L. J., Björner A., “Face numbers of polytopes and complexes”, CRC Handbook on Discrete and Computational Geometry, CRC, Boca Raton, 1997, 291–310 | MR | Zbl

[3] Björner A., “Face numbers of complexes and polytopes”, Proc. Intern. Congress Math., Amer. Math. Soc., Berkeley, 1986 ; Providence, 1987, 1408–1418 | MR | Zbl

[4] Bruns W., Herzog J., Cohen–Macaulay Rings, Cambridge Univ. Press, Cambridge, 1993 | MR | Zbl

[5] Hibi T., Algebraic Combinatorics on Convex Polytopes, Carslaw, Glebe, 1992 | Zbl

[6] Klee V., Kleinschmidt P., “Convex polytopes and related complexes”, Handbook of Combinatorics, I, eds. Graham R. L., Elsevier, Amsterdam, 1995, 875–917 | MR

[7] Stanley R. P., Combinatorics and Commutative Algebra, Birkhäuser, Berlin, 1996 | MR | Zbl

[8] Ziegler G. M., Lectures on Polytopes, Springer, Berlin, 1995 | MR

[9] Björner A., Wachs M., “Shellable nonpure complexes and posets, I, II”, Trans. Amer. Math. Soc., 348 (1996), 1299–1327 ; 349 (1997), 3945–3975 | DOI | MR | Zbl | DOI | MR | Zbl

[10] Stenli R., Perechislitelnaya kombinatorika, Mir, Moskva, 1990 | MR

[11] Duval A. M., “Algebraic shifting and sequentially Cohen–Macaulay simplicial complexes”, Electronic J. Combinatorics, 3:21 (1996) | MR | Zbl

[12] McMullen P., “The maximum number of faces of a convex polytope”, Mathematika, 17 (1970), 179–184 | MR | Zbl

[13] Chari M. K., “Two decompositions in topological combinatorics with applications to matroid complexes”, Trans. Amer. Math. Soc., 349 (1997), 3925–3944 | DOI | MR

[14] Chari M. K., “Steiner complexes, matroid ports, and shellability”, J. Comb. Theory, 59 (1993), 41–68 | DOI | MR | Zbl

[15] Duval A. M., On $f$-Vectors and Relative Homology, Preprint Depart. Math. Sci. Univ. Texas at El Paso, 1997 | MR

[16] Provan J. S., Billera L. J., “Decompositions of simplicial complexes related to diameters of convex polyhedra”, Math. Oper. Res., 5 (1980), 576–594 | DOI | MR | Zbl

[17] Bayer D., Monomial Ideals and Duality, Preprint Depart. Math., Barnard College, Columbia University, 1996

[18] Björner A., Butler L. M., Matveev A. O., “Note on a combinatorial application of Alexander duality”, J. Comb. Theory, 80 (1997), 163–165 | DOI | MR | Zbl

[19] Eagon J. A., Reiner V., “Resolutions of Stanley–Reisner rings and Alexander duality”, J. Pure and Appl. Algebra, 130 (1998), 265–275 | DOI | MR | Zbl

[20] Miller E., Alexander Duality for Monomial Ideals and their Resolutions, , 1998 arXiv: math.AG/9812095

[21] Miller E., Sturmfels B., Yanagawa K., Generic and Cogeneric Monomial Ideals, , 1998 arXiv: math.AG/9812126 | MR

[22] Reiner V., Welker V., Linear Syzygies of Stanley–Reisner Ideals, Preprint School Math., Univ. Minnesota, Minneapolis, 1998

[23] Terai N., Hibi T., “Alexander duality theorem and second Betti numbers of Stanley–Reisner rings”, Adv. Math., 124 (1996), 332–333 | DOI | MR | Zbl

[24] Aigner M., Kombinatornaya teoriya, Mir, Moskva, 1982 | MR

[25] Gulden Ya., Dzhekson D., Perechislitelnaya kombinatorika, Nauka, Moskva, 1990 | MR

[26] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, Moskva, 1982 | MR | Zbl

[27] Barnabei M., Brini A., Rota Dzh.-K., “Teoriya funktsii Mëbiusa”, Uspekhi matem. nauk, 41:3 (1986), 113–157 | MR | Zbl

[28] Geissinger L., “Valuations on distributive lattices. I, II, III”, Archiv Math, 24 (1973), 230–239 ; 337–345 ; 475–481 | DOI | MR | Zbl

[29] Khorn R., Dzhonson Ch., Matrichnyi analiz, 1989, Mir, Moskva | MR

[30] McMullen P., Shephard G. C., Convex Polytopes and the Upper Bound Conjecture, Cambridge Univ. Press, Cambridge, 1971 | MR | Zbl

[31] McMullen P., Walkup D. W., “A generalized lower-bound conjecture for simplicial polytopes”, Mathematika, 18 (1971), 264–273 | MR | Zbl

[32] Stanley R. P., “Hilbert functions of graded algebras”, Adv. Math., 28 (1978), 57–83 | DOI | MR | Zbl

[33] Stanley R. P., “Binomial posets, Möbius inversion and permutation enumeration”, J. Comb. Theory, 20 (1976), 336–356 | DOI | MR | Zbl

[34] Brensted A., Vvedenie v teoriyu vypuklykh mnogogrannikov, Mir, Moskva, 1988 | MR

[35] Kalai G., “Some aspects of the combinatorial theory of convex polytopes”, NATO ASI Ser., Ser. C, Math. Phys. Sci., 440 (1994), 205–229 | MR | Zbl

[36] Grünbaum B, Convex Polytopes, Interscience, London, 1967 | MR | Zbl

[37] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Mnogogranniki. Grafy. Optimizatsiya, Nauka, Moskva, 1981 | MR

[38] Barvinok A. I., “On equivariant generalization of Dehn–Sommerville equations”, European J. Combinatorics, 13 (1992), 419–428 | DOI | MR | Zbl

[39] Bayer M. M., Billera L. J., “Generalized Dehn–Sommerville relations for polytopes, spheres and Eulerian partially ordered sets”, Invent. Math., 79 (1985), 143–157 | DOI | MR | Zbl