Relative Stanley–Reisner theory and Upper Bound Theorems for Minkowski sums

Adiprasito, Karim A.; Sanyal, Raman

doi:10.1007/s10240-016-0083-7

Adiprasito, Karim A.¹ ; Sanyal, Raman ²

¹ Einstein Institute for Mathematics, Hebrew University of Jerusalem Jerusalem Israel
² Fachbereich Mathematik und Informatik, Freie Universität Berlin Berlin Germany

Publications Mathématiques de l'IHÉS, Tome 124 (2016), pp. 99-163.

Résumé

In this paper we settle two long-standing questions regarding the combinatorial complexity of Minkowski sums of polytopes: We give a tight upper bound for the number of faces of a Minkowski sum, including a characterization of the case of equality. We similarly give a (tight) upper bound theorem for mixed facets of Minkowski sums. This has a wide range of applications and generalizes the classical Upper Bound Theorems of McMullen and Stanley.

Our main observation is that within (relative) Stanley–Reisner theory, it is possible to encode topological as well as combinatorial/geometric restrictions in an algebraic setup. We illustrate the technology by providing several simplicial isoperimetric and reverse isoperimetric inequalities in addition to our treatment of Minkowski sums.

MR Zbl

DOI : 10.1007/s10240-016-0083-7

Mots clés : Simplicial Complex, Local Cohomology, Simplicial Polytopes, Local Cohomology Module, Bound Theorem

Affiliations des auteurs :

Adiprasito, Karim A. ¹ ; Sanyal, Raman ²

¹ Einstein Institute for Mathematics, Hebrew University of Jerusalem Jerusalem Israel
² Fachbereich Mathematik und Informatik, Freie Universität Berlin Berlin Germany

@article{PMIHES_2016__124__99_0,
     author = {Adiprasito, Karim A. and Sanyal, Raman},
     title = {Relative {Stanley{\textendash}Reisner} theory and {Upper} {Bound} {Theorems} for {Minkowski} sums},
     journal = {Publications Math\'ematiques de l'IH\'ES},
     pages = {99--163},
     publisher = {Springer Berlin Heidelberg},
     address = {Berlin/Heidelberg},
     volume = {124},
     year = {2016},
     doi = {10.1007/s10240-016-0083-7},
     mrnumber = {3578915},
     zbl = {1368.52016},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1007/s10240-016-0083-7/}
}

TY  - JOUR
AU  - Adiprasito, Karim A.
AU  - Sanyal, Raman
TI  - Relative Stanley–Reisner theory and Upper Bound Theorems for Minkowski sums
JO  - Publications Mathématiques de l'IHÉS
PY  - 2016
SP  - 99
EP  - 163
VL  - 124
PB  - Springer Berlin Heidelberg
PP  - Berlin/Heidelberg
UR  - http://archive.numdam.org/articles/10.1007/s10240-016-0083-7/
DO  - 10.1007/s10240-016-0083-7
LA  - en
ID  - PMIHES_2016__124__99_0
ER  -

%0 Journal Article
%A Adiprasito, Karim A.
%A Sanyal, Raman
%T Relative Stanley–Reisner theory and Upper Bound Theorems for Minkowski sums
%J Publications Mathématiques de l'IHÉS
%D 2016
%P 99-163
%V 124
%I Springer Berlin Heidelberg
%C Berlin/Heidelberg
%U http://archive.numdam.org/articles/10.1007/s10240-016-0083-7/
%R 10.1007/s10240-016-0083-7
%G en
%F PMIHES_2016__124__99_0

Adiprasito, Karim A.; Sanyal, Raman. Relative Stanley–Reisner theory and Upper Bound Theorems for Minkowski sums. Publications Mathématiques de l'IHÉS, Tome 124 (2016), pp. 99-163. doi : 10.1007/s10240-016-0083-7. http://archive.numdam.org/articles/10.1007/s10240-016-0083-7/

Bibliographie
Cité par

[Adi15] K. A. Adiprasito, Toric chordality, preprint, | arXiv | MR

[AB12] K. A. Adiprasito and B. Benedetti, Subdivisions, shellability, and collapsibility of products, Combinatorica, February 2012, to appear, available at | arXiv | MR

[ABG83] K. A. Adiprasito, A. Björner and A. Goodarzi, Face numbers of sequentially Cohen–Macaulay complexes and Betti numbers of componentwise linear ideals, preprint, | arXiv | MR

[ABPS15] K. A. Adiprasito, P. Brinkmann, A. Padrol and R. Sanyal, Mixed faces and colorful depth, 2015, in preparation.

[BKL86] Barnette, D.; Kleinschmidt, P.; Lee, C. W. An upper bound theorem for polytope pairs, Math. Oper. Res., Volume 11 (1986), pp. 451-464 | DOI | MR | Zbl

[BL80] Billera, L. J.; Lee, C. W. Sufficiency of McMullen’s conditions for $f$ -vectors of simplicial polytopes, Bull. Am. Math. Soc., New Ser., Volume 2 (1980), pp. 181-185 | DOI | MR | Zbl

[BL81] Billera, L. J.; Lee, C. W. The numbers of faces of polytope pairs and unbounded polyhedra, Eur. J. Comb., Volume 2 (1981), pp. 307-322 | DOI | MR | Zbl

[Bjö80] Björner, A. Shellable and Cohen-Macaulay partially ordered sets, Trans. Am. Math. Soc., Volume 260 (1980), pp. 159-183 | DOI | MR | Zbl

[Bjö03] Björner, A. Nerves, fibers and homotopy groups, J. Comb. Theory, Ser. A, Volume 102 (2003), pp. 88-93 | DOI | MR | Zbl

[Bjö07] Björner, A. A comparison theorem for $f$ -vectors of simplicial polytopes, Pure Appl. Math. Q., Volume 3 (2007), pp. 347-356 | DOI | MR | Zbl

[BWW05] Björner, A.; Wachs, M. L.; Welker, V. Poset fiber theorems, Trans. Am. Math. Soc., Volume 357 (2005), pp. 1877-1899 | DOI | MR | Zbl

[Bor48] Borsuk, K. On the imbedding of systems of compacta in simplicial complexes, Fundam. Math., Volume 35 (1948), pp. 217-234 | DOI | MR | Zbl

[BM71] Bruggesser, H.; Mani, P. Shellable decompositions of cells and spheres, Math. Scand., Volume 29 (1971), pp. 197-205 (1972) | DOI | MR | Zbl

[BH93] Bruns, W.; Herzog, J. Cohen-Macaulay Rings (1993) | MR | Zbl

[Buc43] Buck, R. C. Partition of space, Am. Math. Mon., Volume 50 (1943), pp. 541-544 | DOI | MR | Zbl

[CD95] Charney, R. M.; Davis, M. W. Strict hyperbolization, Topology, Volume 34 (1995), pp. 329-350 | DOI | MR | Zbl

[CLS11] Cox, D. A.; Little, J. B.; Schenck, H. K. Toric Varieties (2011) | MR | Zbl

[Dav08] Davis, M. W. The Geometry and Topology of Coxeter Groups (2008) | MR | Zbl

[dLRS10] de Loera, J. A.; Rambau, J.; Santos, F. Triangulations (2010) (Structures for algorithms and applications) | DOI | MR | Zbl

[Duv96] Duval, A. M. Algebraic shifting and sequentially Cohen-Macaulay simplicial complexes, Electron. J. Comb., Volume 3 (1996), p. 14 (research paper r21) | MR | Zbl

[Eis95] Eisenbud, D. Commutative Algebra with a View Toward Algebraic Geometry (1995) | MR | Zbl

[EC95] Emiris, I. Z.; Canny, J. F. Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symb. Comput., Volume 20 (1995), pp. 117-149 | DOI | MR | Zbl

[FW07] Fukuda, K.; Weibel, C. $f$ -Vectors of Minkowski additions of convex polytopes, Discrete Comput. Geom., Volume 37 (2007), pp. 503-516 | DOI | MR | Zbl

[FW10] Fukuda, K.; Weibel, C. A linear equation for Minkowski sums of polytopes relatively in general position, Eur. J. Comb., Volume 31 (2010), pp. 565-573 | DOI | MR | Zbl

[FS97] Fulton, W.; Sturmfels, B. Intersection theory on toric varieties, Topology, Volume 36 (1997), pp. 335-353 | DOI | MR | Zbl

[Geo08] Geoghegan, R. Topological Methods in Group Theory (2008) | DOI | MR | Zbl

[Grä87] Gräbe, H.-G. Generalized Dehn-Sommerville equations and an upper bound theorem, Beitr. Algebra Geom., Volume 25 (1987), pp. 47-60 | MR | Zbl

[GS93] Gritzmann, P.; Sturmfels, B. Minkowski addition of polytopes: computational complexity and applications to Gröbner bases, SIAM J. Discrete Math., Volume 6 (1993), pp. 246-269 | DOI | MR | Zbl

[Hib91] Hibi, T. Quotient algebras of Stanley-Reisner rings and local cohomology, J. Algebra, Volume 140 (1991), pp. 336-343 | DOI | MR | Zbl

[Hoc77] Hochster, M. Cohen-Macaulay rings, combinatorics, and simplicial complexes, Ring Theory, II (1977), pp. 171-223 | MR | Zbl

[HR74] Hochster, M.; Roberts, J. L. Rings of invariants of reductive groups acting on regular rings are Cohen-Macaulay, Adv. Math., Volume 13 (1974), pp. 115-175 | DOI | MR | Zbl

[Hov78] Hovanskiĭ, A. G. Newton polyhedra, and the genus of complete intersections, Funkc. Anal. Prilozh., Volume 12 (1978), pp. 51-61 | MR | Zbl

[ILL+07] Iyengar, S. B.; Leuschke, G. J.; Leykin, A.; Miller, C.; Miller, E.; Singh, A. K.; Walther, U. Twenty-Four Hours of Local Cohomology (2007) | MR | Zbl

[JMR83] Julian, W.; Mines, R.; Richman, F. Alexander duality, Pac. J. Math., Volume 106 (1983), pp. 115-127 | DOI | MR | Zbl

[Kal91] Kalai, G. The diameter of graphs of convex polytopes and $f$ -vector theory, Applied Geometry and Discrete Mathematics (1991), pp. 387-411 | MR | Zbl

[KKT15] Karavelas, M. I.; Konaxis, C.; Tzanaki, E. The maximum number of faces of the Minkowski sum of three convex polytopes, J. Comput. Geom., Volume 6 (2015), pp. 21-74 | MR | Zbl

[KT11] M. I. Karavelas and E. Tzanaki, The maximum number of faces of the Minkowski sum of two convex polytopes, preprint, (2011), Discrete Comput. Geom., to appear, available at doi:. | DOI | MR | Zbl

[KT15] Karavelas, M. I.; Tzanaki, E. A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes, 31st International Symposium on Computational Geometry, LIPIcs (2015), pp. 81-95 | MR | Zbl

[Kat12] Katz, E. Tropical intersection theory from toric varieties, Collect. Math., Volume 63 (2012), pp. 29-44 | DOI | MR | Zbl

[KK79] Kind, B.; Kleinschmidt, P. Schälbare Cohen-Macauley-Komplexe und ihre Parametrisierung, Math. Z., Volume 167 (1979), pp. 173-179 | DOI | MR | Zbl

[Kle64] Klee, V. On the number of vertices of a convex polytope, Can. J. Math., Volume 16 (1964), pp. 701-720 | DOI | MR | Zbl

[Lat91] Latombe, J-C. Robot Motion Planning (1991) | DOI | Zbl

[MPP11] Matschke, B.; Pfeifle, J.; Pilaud, V. Prodsimplicial-neighborly polytopes, Discrete Comput. Geom., Volume 46 (2011), pp. 100-131 | DOI | MR | Zbl

[McM70] McMullen, P. The maximum numbers of faces of a convex polytope, Mathematika, Volume 17 (1970), pp. 179-184 | DOI | MR | Zbl

[McM04] McMullen, P. Triangulations of simplicial polytopes, Beitr. Algebra Geom., Volume 45 (2004), pp. 37-46 | MR | Zbl

[MW71] McMullen, P.; Walkup, D. W. A generalized lower-bound conjecture for simplicial polytopes, Mathematika, Volume 18 (1971), pp. 264-273 | DOI | MR | Zbl

[MNS11] Miller, E.; Novik, I.; Swartz, E. Face rings of simplicial complexes with singularities, Math. Ann., Volume 351 (2011), pp. 857-875 | DOI | MR | Zbl

[MS05] Miller, E.; Sturmfels, B. Combinatorial Commutative Algebra (2005) | MR | Zbl

[Min11] Minkowski, H. Theorie der konvexen körper, insbesondere Begründung ihres Oberflächenbegriffs, Gesammelte Abh. Hermann Minkowski, Volume 2 (1911), pp. 131-229

[Miy89] Miyazaki, M. Characterizations of Buchsbaum complexes, Manuscr. Math., Volume 63 (1989), pp. 245-254 | DOI | MR | Zbl

[Mot57] Motzkin, T. S. Comonotone curves and polyhedra, Bull. Am. Math. Soc., Volume 63 (1957), p. 35 | DOI | MR

[MRTT53] Motzkin, T. S.; Raiffa, H.; Thompson, G. L.; Thrall, R. M. The double description method, Contributions to the Theory of Games (1953), pp. 51-73 | MR | Zbl

[Nov03] Novik, I. Remarks on the upper bound theorem, J. Comb. Theory, Ser. A, Volume 104 (2003), pp. 201-206 | DOI | MR | Zbl

[Nov05] Novik, I. On face numbers of manifolds with symmetry, Adv. Math., Volume 192 (2005), pp. 183-208 | DOI | MR | Zbl

[NS09] Novik, I.; Swartz, E. Applications of Klee’s Dehn–Sommerville relations, Discrete Comput. Geom., Volume 42 (2009), pp. 261-276 | DOI | MR | Zbl

[NS12] Novik, I.; Swartz, E. Face numbers of pseudomanifolds with isolated singularities, Math. Scand., Volume 110 (2012), pp. 198-222 | DOI | MR | Zbl

[PS93] Pedersen, P.; Sturmfels, B. Product formulas for resultants and Chow forms, Math. Z., Volume 214 (1993), pp. 377-396 | DOI | MR | Zbl

[Rei76] Reisner, G. A. Cohen-Macaulay quotients of polynomial rings, Adv. Math., Volume 21 (1976), pp. 30-49 | DOI | MR | Zbl

[RS72] Rourke, C. P.; Sanderson, B. J. Introduction to Piecewise-Linear Topology (1972) | DOI | MR | Zbl

[San09] Sanyal, R. Topological obstructions for vertex numbers of Minkowski sums, J. Comb. Theory, Ser. A, Volume 116 (2009), pp. 168-179 | DOI | MR | Zbl

[Sch81] Schenzel, P. On the number of faces of simplicial complexes and the purity of Frobenius, Math. Z., Volume 178 (1981), pp. 125-142 | DOI | MR | Zbl

[Sch82] Schenzel, P. Dualisierende Komplexe in der lokalen Algebra und Buchsbaum-Ringe (1982) (with an English summary) | DOI | MR | Zbl

[Sch93] Schneider, R. Convex Bodies: The Brunn-Minkowski Theory (1993) | DOI | MR | Zbl

[Sta75] Stanley, R. P. The upper bound conjecture and Cohen-Macaulay rings, Stud. Appl. Math., Volume 54 (1975), pp. 135-142 | DOI | MR | Zbl

[Sta87] Stanley, R. P. Generalized $H$ -vectors, intersection cohomology of toric varieties, and related results, Commutative Algebra and Combinatorics (1987), pp. 187-213 | DOI | MR | Zbl

[Sta93] Stanley, R. P. A monotonicity property of $h$ -vectors and $h^{*}$ -vectors, Eur. J. Comb., Volume 14 (1993), pp. 251-258 | DOI | MR | Zbl

[Sta96] Stanley, R. P. Combinatorics and Commutative Algebra (1996) | MR | Zbl

[ST10] Steffens, R.; Theobald, T. Combinatorics and genus of tropical intersections and Ehrhart theory, SIAM J. Discrete Math., Volume 24 (2010), pp. 17-32 | DOI | MR | Zbl

[Ste26] Steiner, J. Einige Gesetze über die Theilung der Ebene und des Raumes, J. Reine Angew. Math., Volume 1 (1826), pp. 349-364 | DOI | MR | Zbl

[Stu02] Sturmfels, B. Solving Systems of Polynomial Equations (2002) | DOI | MR | Zbl

[Swa05] Swartz, E. Lower bounds for $h$ -vectors of $k$ -CM, independence, and broken circuit complexes, SIAM J. Discrete Math., Volume 18 (2005), pp. 647-661 | DOI | MR | Zbl

[Wei12] Weibel, C. Maximal $f$ -vectors of Minkowski sums of large numbers of polytopes, Discrete Comput. Geom., Volume 47 (2012), pp. 519-537 | DOI | MR | Zbl

[Zee66] Zeeman, E. C. Seminar on Combinatorial Topology (1966) | Zbl

[Zie95] Ziegler, G. M. Lectures on Polytopes (1995) (Revised edition, 1998; seventh updated printing 2007) | DOI | Zbl

Cité par Sources :