zbMATH — the first resource for mathematics

Unconditional reflexive polytopes. (English) Zbl 07242486
A convex polytope $$P \subset \mathbb{R}^d$$ is called unconditional if $$(\sigma_1 p_1 , \dots, \sigma_d p_d) \in P$$ for all $$(p_1,\dots,p_d) \in P$$ and all $$(\sigma_1,\dots,\sigma_d)\in \{\pm 1\}^d$$. The paper under review studies unconditional polytopes from the viewpoint of discrete geometry and combinatorial commutative algebra. In particular, it is shown that a lattice polytope $$P$$ is an unconditional reflexive polytope if and only if $$P$$ is obtained from the stable set polytope of a perfect graph. As examples, some special lattice polytopes are studied: type-B Birkhoff polytopes, signed Birkhoff polytopes, lattice polytopes arising from perfect CIS graphs, and unconditional chain polytopes of posets. Note that unconditional chain polytopes of posets were independently introduced in [H. Ohsugi and A. Tsuchiya, Isr. J. Math. 237, No. 1, 485–500 (2020; Zbl 07212851)]under the name “enriched chain polytopes”, and the same Gröbner bases of such polytopes were constructed there.
MSC:
 52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) 52B12 Special polytopes (linear programming, centrally symmetric, etc.)
Software:
birkhoff faces; Normaliz; OEIS
Full Text:
References:
 [1] Adiprasito, K.; Huh, J.; Katz, E., Hodge theory for combinatorial geometries, Ann. Math., 188, 2, 381-452 (2018) · Zbl 1442.14194 [2] Andrade, D.V., Boros, E., Gurvich, V.: On graphs whose maximal cliques and stable sets intersect. In: Optimization Problems in Graph Theory. Springer Optim. Appl., vol. 139, pp. 3-63. Springer, Cham (2018) · Zbl 1416.05203 [3] Artstein-Avidan, S., Sadovsky, S., Sanyal, R.: Volume and mixed volume inequalities for locally anti-blocking bodies (2020, in preparation) [4] Athanasiadis, Ch.A.: Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley. J. Reine Angew. Math. 583, 163-174 (2005) · Zbl 1077.52011 [5] Bapat, R.B., Raghavan, T.E.S.: Nonnegative Matrices and Applications. Encyclopedia of Mathematics and its Applications, vol. 64. Cambridge University Press, Cambridge (1997) · Zbl 0879.15015 [6] Batyrev, VV, Dual polyhedra and mirror symmetry for Calabi-Yau hypersurfaces in toric varieties, J. Algebr. Geom., 3, 3, 493-535 (1994) · Zbl 0829.14023 [7] Beck, M.; Haase, Ch; Sam, SV, Grid graphs, Gorenstein polytopes, and domino stackings, Graphs Comb., 25, 4, 409-426 (2009) · Zbl 1189.05142 [8] Beck, M.; Pixton, D., The Ehrhart polynomial of the Birkhoff polytope, Discrete Comput. Geom., 30, 4, 623-637 (2003) · Zbl 1065.52007 [9] Beck, M.; Robins, S., Computing the Continuous Discretely (2015), New York: Springer, New York [10] Beck, M.; Sanyal, R., Combinatorial Reciprocity Theorems (2018), Providence: American Mathematical Society, Providence · Zbl 1411.05001 [11] Birkhoff, G., Three observations on linear algebra, Univ. Nac. Tucumán. Rev. A, 5, 147-151 (1946) [12] Björner, A.; Brenti, F., Combinatorics of Coxeter Groups (2005), New York: Springer, New York · Zbl 1110.05001 [13] Bollobás, B.; Brightwell, GR, Convex bodies, graphs and partial orders, Proc. Lond. Math. Soc., 80, 2, 415-450 (2000) · Zbl 1029.52002 [14] Brazitikos, S.; Giannopoulos, A.; Valettas, P.; Vritsiou, B-H, Geometry of Isotropic Convex Bodies (2014), Providence: American Mathematical Society, Providence · Zbl 1304.52001 [15] Brenti, F.: Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update. In: Jerusalem Combinatorics ’93. Contemp. Math., vol. 178, pp. 71-89. American Mathematical Society, Providence (1994) · Zbl 0813.05007 [16] Bruns, W.; Gubeladze, J., Normality and covering properties of affine semigroups, J. Reine Angew. Math., 510, 161-178 (1999) · Zbl 0937.20036 [17] Bruns, W.; Gubeladze, J., Polytopes, Rings, and $$K$$-Theory (2009), Dordrecht: Springer, Dordrecht [18] Bruns, W., Ichim, B., Römer, T., Sieg, R., Söger, Ch.: Normaliz. Algorithms for rational cones and affine monoids. https://www.normaliz.uni-osnabrueck.de [19] Bruns, W.; Römer, T., $$h$$-vectors of Gorenstein polytopes, J. Comb. Theory Ser. A, 114, 1, 65-76 (2007) · Zbl 1108.52013 [20] Canfield, E.R., McKay, B.D.: The asymptotic volume of the Birkhoff polytope. Online J. Anal. Comb. 4 (2009) · Zbl 1193.15034 [21] Chappell, T.; Friedl, T.; Sanyal, R., Two double poset polytopes, SIAM J. Discrete Math., 31, 4, 2378-2413 (2017) · Zbl 1425.52011 [22] Cox, DA, Mirror symmetry and polar duality of polytopes, Symmetry, 7, 3, 1633-1645 (2015) · Zbl 1377.14009 [23] Cox, DA; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms, Undergraduate Texts in Mathematics (2015), Cham: Springer, Cham [24] Davis, R., Ehrhart series of polytopes related to symmetric doubly-stochastic matrices, Electron. J. Comb., 22, 2, 17 (2015) · Zbl 1311.05012 [25] De Loera, JA; Liu, F.; Yoshida, R., A generating function for all semi-magic squares and the volume of the Birkhoff polytope, J. Algebr. Comb., 30, 1, 113-139 (2009) · Zbl 1187.05009 [26] De Loera, JA; Rambau, J.; Santos, F., Triangulations (2010), Berlin: Springer, Berlin [27] De Negri, E.; Hibi, T., Gorenstein algebras of Veronese type, J. Algebra, 193, 2, 629-639 (1997) · Zbl 0884.13012 [28] Dobson, E.; Hujdurović, A.; Milanič, M.; Verret, G., Vertex-transitive CIS graphs, Eur. J. Comb., 44, A, 87-98 (2015) · Zbl 1302.05077 [29] Ehrenborg, R.; Hetyei, G.; Readdy, M., Simion’s type $$B$$ associahedron is a pulling triangulation of the Legendre polytope, Discrete Comput. Geom., 60, 1, 98-114 (2018) · Zbl 1395.52014 [30] Ehrhart, E., Sur les polyèdres rationnels homothétiques a $$n$$ dimensions, C. R. Acad. Sci. Paris, 254, 616-618 (1962) · Zbl 0100.27601 [31] Freij, R.; Henze, M.; Schmitt, MW; Ziegler, GM, Face numbers of centrally symmetric polytopes produced from split graphs, Electron. J. Comb., 20, 2, 32 (2013) [32] Fritsch, K., Heuer, J., Sanyal, R., Schulz, N.: The Martin Gardner polytopes. Am. Math. Mon. (accepted) · Zbl 1444.05003 [33] Fulkerson, DR, Blocking and anti-blocking pairs of polyhedra, Math. Program., 1, 168-194 (1971) · Zbl 0254.90054 [34] Fulkerson, DR, Anti-blocking polyhedra, J. Comb. Theory Ser. B, 12, 50-71 (1972) · Zbl 0227.05015 [35] Grillet, PA, Maximal chains and antichains, Fund. Math., 65, 157-167 (1969) · Zbl 0191.00601 [36] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1993), Berlin: Springer, Berlin · Zbl 0837.05001 [37] Haase, Ch., Paffenholz, A., Piechnik, L.C., Santos, F.: Existence of unimodular triangulations – positive results (2017). arXiv:1405.1687 [38] Henk, M., Richter-Gebert, J., Ziegler, G.M.: Basic properties of convex polytopes. In: Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.): Handbook of Discrete and Computational Geometry, 3rd ed. CRC Press Ser. Discrete Math. Appl., pp. 383-413. CRC Press, Boca Raton (2017) · Zbl 0911.52007 [39] Hetyei, G., Delannoy orthants of Legendre polytopes, Discrete Comput. Geom., 42, 4, 705-721 (2009) · Zbl 1200.05015 [40] Hibi, T.: Distributive lattices, affine semigroup rings and algebras with straightening laws. In: Commutative Algebra and Combinatorics (Kyoto 1985). Adv. Stud. Pure Math., vol. 11, pp. 93-109. North-Holland, Amsterdam (1987) [41] Hibi, T., Dual polytopes of rational convex polytopes, Combinatorica, 12, 2, 237-240 (1992) · Zbl 0758.52009 [42] Hibi, T., Matsuda, K., Tsuchiya, A.: Gorenstein Fano polytopes arising from order polytopes and chain polytopes (2015). arXiv:1507.03221 [43] Hofmann, J.: Three Interesting Lattice Polytope Problems. PhD thesis, Freie Universität, Berlin (2018). https://refubium.fu-berlin.de/ [44] Hougardy, S., Classes of perfect graphs, Discrete Math., 306, 19-20, 2529-2571 (2006) · Zbl 1104.05029 [45] Kreuzer, M.; Skarke, H., Classification of reflexive polyhedra in three dimensions, Adv. Theor. Math. Phys., 2, 4, 853-871 (1998) · Zbl 0934.52006 [46] Kreuzer, M.; Skarke, H., Complete classification of reflexive polyhedra in four dimensions, Adv. Theor. Math. Phys., 4, 6, 1209-1230 (2000) · Zbl 1017.52007 [47] Lagarias, JC; Ziegler, GM, Bounds for lattice polytopes containing a fixed number of interior points in a sublattice, Canad. J. Math., 43, 5, 1022-1035 (1991) · Zbl 0752.52010 [48] Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 3, 253-267 (1972) · Zbl 0239.05111 [49] Maffray, F., Kernels in perfect line-graphs, J. Comb. Theory Ser. B, 55, 1, 1-8 (1992) · Zbl 0694.05054 [50] McCarthy, N.; Ogilvie, D.; Spitkovsky, I.; Zobin, N., Birkhoff’s theorem and convex hulls of Coxeter groups, Linear Algebra Appl., 347, 219-231 (2002) · Zbl 1042.51011 [51] Meyer, M., Une caractérisation volumique de certains espaces normés de dimension finie, Israel J. Math., 55, 3, 317-326 (1986) · Zbl 0629.46023 [52] von Neumann, J.: A certain zero-sum two-person game equivalent to the optimal assignment problem. In: Contributions to the Theory of Games, vol. 2. Annals of Mathematics Studies, vol. 28, pp. 5-12. Princeton University Press, Princeton (1953) · Zbl 0050.14105 [53] Oda, T.: Problems on Minkowski sums of convex lattice polytopes (2008). arXiv:0812.1418 [54] Ohsugi, H., Gorenstein cut polytopes, Eur. J. Comb., 38, 122-129 (2014) · Zbl 1286.52005 [55] Ohsugi, H.; Hibi, T., Convex polytopes all of whose reverse lexicographic initial ideals are squarefree, Proc. Am. Math. Soc., 129, 9, 2541-2546 (2001) · Zbl 0984.13014 [56] Ohsugi, H.; Hibi, T., Special simplices and Gorenstein toric rings, J. Comb. Theory Ser. A, 113, 4, 718-725 (2006) · Zbl 1095.13023 [57] Ohsugi, H.; Hibi, T., Reverse lexicographic squarefree initial ideals and Gorenstein Fano polytopes, J. Commut. Algebra, 10, 2, 171-186 (2018) · Zbl 1420.13063 [58] Ohsugi, H., Tsuchiya, A.: Enriched chain polytopes (2019). arXiv:1812.02097 · Zbl 07212851 [59] Paffenholz, A., Faces of Birkhoff polytopes, Electron. J. Comb., 22, 1, 1.67 (2015) · Zbl 1311.52015 [60] Reisner, S., Minimal volume-product in Banach spaces with a $$1$$-unconditional basis, J. Lond. Math. Soc., 36, 1, 126-136 (1987) · Zbl 0598.46010 [61] Saint-Raymond, J.: Sur le volume des corps convexes symétriques. In: Initiation Seminar on Analysis: G. Choquet—M. Rogalski—J. Saint-Raymond, 20th Year: 1980/1981. Publ. Math. Univ. Pierre et Marie Curie, vol. 46, # 11. Univ. Paris VI, Paris (1981) · Zbl 0531.52006 [62] Sanyal, R.; Werner, A.; Ziegler, GM, On Kalai’s conjectures concerning centrally symmetric polytopes, Discrete Comput. Geom., 41, 2, 183-198 (2009) · Zbl 1168.52013 [63] Schneider, R.: Convex Bodies: the Brunn-Minkowski Theory, 2nd ed. Encyclopedia of Mathematics and Its Applications, vol. 151. Cambridge University Press, Cambridge (2014) [64] Schrijver, A., Theory of Linear and Integer Programming (1986), Chichester: Wiley, Chichester · Zbl 0665.90063 [65] Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences (May 2019). https://oeis.org · Zbl 1044.11108 [66] Stanley, RP, Hilbert functions of graded algebras, Adv. Math., 28, 1, 57-83 (1978) · Zbl 0384.13012 [67] Stanley, RP, Decompositions of rational convex polytopes, Ann. Discrete Math., 6, 333-342 (1980) · Zbl 0812.52012 [68] Stanley, RP, Two poset polytopes, Discrete Comput. Geom., 1, 1, 9-23 (1986) · Zbl 0595.52008 [69] Stanley, R.P.: Log-concave and unimodal sequences in algebra, combinatorics, and geometry. In: Graph Theory and Its Applications: East and West (Jinan 1986). Ann. New York Acad. Sci., vol. 576, pp. 500-535. New York Acad. Sci., New York (1989) · Zbl 0792.05008 [70] Stanley, RP, A monotonicity property of $$h$$-vectors and $$h^*$$-vectors, Eur. J. Comb., 14, 3, 251-258 (1993) · Zbl 0799.52008 [71] Sturmfels, B., Gröbner Bases and Convex Polytopes (1996), Providence: American Mathematical Society, Providence · Zbl 0856.13020 [72] Sullivant, S., Compressed polytopes and statistical disclosure limitation, Tohoku Math. J., 58, 3, 433-445 (2006) · Zbl 1121.52028 [73] Tagami, M., Gorenstein polytopes obtained from bipartite graphs, Electron. J. Comb., 17, 8 (2010) · Zbl 1194.52013 [74] Zang, W.: Generalizations of Grillet’s theorem on maximal stable sets and maximal cliques in graphs. Discrete Math. 143(1-3), 259-268 (1995) · Zbl 0831.05036 [75] Ziegler, GM, Lectures on Polytopes (1995), New York: Springer, New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.