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 = {https://www.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  - https://www.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 https://www.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. https://www.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

Das, Sandip; Dev, Subhadeep Ranjan; Sarvottamananda A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes, Discrete Applied Mathematics, Volume 350 (2024), p. 44 | DOI:10.1016/j.dam.2024.02.004
Black, Alexander E.; De Loera, Jesús A.; Lütjeharms, Niklas; Sanyal, Raman The Polyhedral Geometry of Pivot Rules and Monotone Paths, SIAM Journal on Applied Algebra and Geometry, Volume 7 (2023) no. 3, p. 623 | DOI:10.1137/22m1475910
Montúfar, Guido; Ren, Yue; Zhang, Leon Sharp Bounds for the Number of Regions of Maxout Networks and Vertices of Minkowski Sums, SIAM Journal on Applied Algebra and Geometry, Volume 6 (2022) no. 4, p. 618 | DOI:10.1137/21m1413699
Das, Sandip; Dev, Subhadeep Ranjan; Sarvottamananda, Swami A Worst-Case Optimal Algorithm to Compute the Minkowski Sum of Convex Polytopes, Algorithms and Discrete Applied Mathematics, Volume 12601 (2021), p. 179 | DOI:10.1007/978-3-030-67899-9_14
Santamaría-Galvis, Andrés; Woodroofe, Russ Shellings from Relative Shellings, with an Application to NP-Completeness, Discrete Computational Geometry, Volume 66 (2021) no. 2, p. 792 | DOI:10.1007/s00454-020-00273-1
Martínez-Sandoval, Leonardo; Padrol, Arnau The convex dimension of hypergraphs and the hypersimplicial Van Kampen-Flores Theorem, Journal of Combinatorial Theory, Series B, Volume 149 (2021), p. 23 | DOI:10.1016/j.jctb.2021.01.003
Nevo, Eran; Pineda-Villavicencio, Guillermo; Ugon, Julien; Yost, David Almost Simplicial Polytopes: The Lower and Upper Bound Theorems, Canadian Journal of Mathematics, Volume 72 (2020) no. 2, p. 537 | DOI:10.4153/s0008414x18000123
Conforti, Michele; Di Summa, Marco; Faenza, Yuri Balas formulation for the union of polytopes is optimal, Mathematical Programming, Volume 180 (2020) no. 1-2, p. 311 | DOI:10.1007/s10107-018-01358-9
Dao, Hailong; Doolittle, Joseph; Lyle, Justin Minimal Cohen–Macaulay Simplicial Complexes, SIAM Journal on Discrete Mathematics, Volume 34 (2020) no. 3, p. 1602 | DOI:10.1137/19m1275164
Deza, Antoine; Pournin, Lionel Diameter, Decomposability, and Minkowski Sums of Polytopes, Canadian Mathematical Bulletin, Volume 62 (2019) no. 4, p. 741 | DOI:10.4153/s0008439518000668
Adiprasito, Karim A; Brinkmann, Philip; Padrol, Arnau; Paták, Pavel; Patáková, Zuzana; Sanyal, Raman Colorful Simplicial Depth, Minkowski Sums, and Generalized Gale Transforms, International Mathematics Research Notices, Volume 2019 (2019) no. 6, p. 1894 | DOI:10.1093/imrn/rnx184
Adiprasito, Karim; Babaee, Farhad Convexity of complements of tropical varieties, and approximations of currents, Mathematische Annalen, Volume 373 (2019) no. 1-2, p. 237 | DOI:10.1007/s00208-018-1728-2
Bayer, M. M. Graphs, skeleta and reconstruction of polytopes, Acta Mathematica Hungarica, Volume 155 (2018) no. 1, p. 61 | DOI:10.1007/s10474-018-0804-0
Murai, Satoshi; Novik, Isabella; Yoshida, Ken-ichi A duality in Buchsbaum rings and triangulated manifolds, Algebra Number Theory, Volume 11 (2017) no. 3, p. 635 | DOI:10.2140/ant.2017.11.635
Murai, Satoshi; Novik, Isabella Face numbers and the fundamental group, Israel Journal of Mathematics, Volume 222 (2017) no. 1, p. 297 | DOI:10.1007/s11856-017-1591-y
Karavelas, Menelaos I.; Tzanaki, Eleni A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes, Discrete Computational Geometry, Volume 56 (2016) no. 4, p. 966 | DOI:10.1007/s00454-016-9818-y
Murai, Satoshi; Novik, Isabella Face Numbers of Manifolds with Boundary, International Mathematics Research Notices (2016), p. rnw084 | DOI:10.1093/imrn/rnw084

Cité par 17 documents. Sources : Crossref