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

Karim A. Adiprasito; Raman Sanyal

doi:10.1007/s10240-016-0083-7

Karim A. Adiprasito ¹ ; Raman Sanyal ²

¹ 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, Volume 124 (2016), pp. 99-163

Abstract

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.

Received: 2014-11-25
Accepted: 2016-02-22
Online First: 2016-03-23
Published online: 2016-11-07

MR Zbl

DOI: 10.1007/s10240-016-0083-7

Keywords: Simplicial Complex, Local Cohomology, Simplicial Polytopes, Local Cohomology Module, Bound Theorem

Author's affiliations:

Karim A. Adiprasito ¹; Raman Sanyal ²

¹ 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 = {Karim A. Adiprasito and Raman Sanyal},
     title = {Relative {Stanley{\textendash}Reisner} theory and {Upper} {Bound} {Theorems} for {Minkowski} sums},
     journal = {Publications Math\'ematiques de l'IH\'ES},
     pages = {99--163},
     year = {2016},
     publisher = {Springer Berlin Heidelberg},
     address = {Berlin/Heidelberg},
     volume = {124},
     doi = {10.1007/s10240-016-0083-7},
     mrnumber = {3578915},
     zbl = {1368.52016},
     language = {en},
     url = {https://pmihes.centre-mersenne.org/articles/10.1007/s10240-016-0083-7/}
}

TY  - JOUR
AU  - Karim A. Adiprasito
AU  - Raman Sanyal
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  - https://pmihes.centre-mersenne.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 Karim A. Adiprasito
%A Raman Sanyal
%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 https://pmihes.centre-mersenne.org/articles/10.1007/s10240-016-0083-7/
%R 10.1007/s10240-016-0083-7
%G en
%F PMIHES_2016__124__99_0

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

References
Cited by

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[KKT15] M. I. Karavelas; C. Konaxis; E. Tzanaki 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] M. I. Karavelas; E. Tzanaki 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] E. Katz Tropical intersection theory from toric varieties, Collect. Math., Volume 63 (2012), pp. 29-44 | MR | DOI | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cited by Sources: