×

Enumeration of 2-level polytopes. (English) Zbl 1414.05023

A polytope is the convex hull of finitely many points in \(\mathbb{R}^d\). A hyperplane \(H \subset\mathbb{R}^d\) is a supporting hyperplane for the polytope \(P\) if \(P\) lies entirely on one of the two half spaces defined by \(H\). A facet of \(P\) is a set \(P \cap H\), for some supporting hyperplane \(H\), that has dimension 1 smaller than that of \(P\), and a vertex of \(P\) is a point of the form \(P \cap H\) for some supporting hyperplane \(H\).
A polytope \(P\) is 2-level if, for any facet supporting hyperplane \(H\), the vertices of \(P\) that are not on \(H\) are all in one specific translate of \(H\). (2-level polytopes are also called compressed.) 2-level polytopes have several applications, e.g., in combinatorial optimization and communication complexity.
The paper under review gives an algorithm to enumerate all 2-level polytopes (up to combinatorial type) in a given dimension, and the authors used their algorithm to build a database of 2-level polytopes of dimension \(\le 7\). The algorithm is recursive, using the fact that every facet of a 2-level polytope is again 2-level.

MSC:

05A15 Exact enumeration problems, generating functions
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
05C17 Perfect graphs
52B55 Computational aspects related to convexity
68W05 Nonnumerical algorithms
90C22 Semidefinite programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aichholzer, O.; Ziegler, G. (ed.); Kalai, G. (ed.), Extremal properties of 0/1-polytopes of dimension 5, 111-130 (2000), Birkhäuser · Zbl 0966.52011
[2] Aprile, M., Cevallos, A., Faenza, Y.: On 2-level polytopes arising in combinatorial settings. SIAM J. Discret. Math. 32, 1857-1886 (2018) · Zbl 1395.52018 · doi:10.1137/17M1116684
[3] Birkhoff, G.: Lattice Theory (American Mathematical Society Colloquium Publications), vol. 25, no. 2. American Mathematical Society (1940) · JFM 66.0100.04
[4] Birkhoff, G.: Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumán Rev. Ser. A 5, 147-151 (1946)
[5] Blekherman, G.: Nonnegative polynomials and sums of squares. J. Am. Math. Soc. 25(3), 617-635 (2012) · Zbl 1258.14067 · doi:10.1090/S0894-0347-2012-00733-4
[6] Bohn, A.; Faenza, Y.; Fiorini, S.; Fisikopoulos, V.; Macchia, M.; Pashkovich, K.; Bansal, N. (ed.); Finocchi, I. (ed.), Enumeration of 2-level polytopes, No. 9294, 191-202 (2015), Berlin · Zbl 1394.52008
[7] Caspard, Nathalie, Monjardet, Bernard: The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey. Discrete Appl. Math. 127(2), 241-269 (2003) · Zbl 1026.06008 · doi:10.1016/S0166-218X(02)00209-3
[8] Chvátal, V.: On certain polytopes associated with graphs. J. Comb. Theory Ser. B 18, 138-154 (1975) · Zbl 0277.05139 · doi:10.1016/0095-8956(75)90041-6
[9] Cornuéjols, G.: Combinatorial Optimization: Packing and Covering. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (2001)
[10] De Loera, J., Rambau, J., Santos, F.: Triangulations, vol. 25. Springer, Berlin (2010) · Zbl 1207.52002
[11] Fiorini, S., Fisikopoulos, V., Macchia, M.: Two-level polytopes with a prescribed facet. In: Combinatorial Optimization - 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, 16-18 May 2016, Revised Selected Papers, pp. 285-296. https://doi.org/10.1007/978-3-319-45587-7_25 · Zbl 1397.52008
[12] Fukuda, K., Miyata, H., Moriyama, S.: Complete enumeration of small realizable oriented matroids. Discrete Comput. Geom. 49(2), 359-381 (2013). (English) · Zbl 1278.52014 · doi:10.1007/s00454-012-9470-0
[13] Ganter, B.; Ganter, B. (ed.); Wille, R. (ed.); Wolff, KE (ed.), Algorithmen zur Formalen Begriffsanalyse, 241-254 (1987), Wien · Zbl 0812.68045
[14] Ganter, B., Reuter, K.: Finding all closed sets: a general approach. Order 8(3), 283-290 (1991). (English) · Zbl 0754.06003 · doi:10.1007/BF00383449
[15] Ganter, B., Wille, R.: Formal Concept Analysis—Mathematical Foundations. Springer, Berlin (1999) · Zbl 0909.06001 · doi:10.1007/978-3-642-59830-2
[16] Gillis, N., Glineur, F.: On the geometric interpretation of the nonnegative rank. Linear Algebra Appl. 437(11), 2685-2712 (2012) · Zbl 1258.65039 · doi:10.1016/j.laa.2012.06.038
[17] Gouveia, J., Grappe, R., Kaibel, V., Pashkovich, K., Robinson, R.Z., Thomas, R.R.: Which nonnegative matrices are slack matrices? Linear Algebra Appl. 439(10), 2921-2933 (2013) · Zbl 1283.15103 · doi:10.1016/j.laa.2013.08.009
[18] Gouveia, J., Parrilo, P., Thomas, R.: Theta bodies for polynomial ideals. SIAM J. Optim. 20(4), 2097-2118 (2010) · Zbl 1213.90190 · doi:10.1137/090746525
[19] Gouveia, J., Pashkovich, K., Robinson, R.Z., Thomas, R.R.: Four dimensional polytopes of minimum positive semidefinite rank. J. Comb. Theory Ser. A 145, 184-226 (2017) · Zbl 1360.52006
[20] Gouveia, J., Robinson, R., Thomas, R.: Polytopes of minimum positive semidefinite rank. Discrete Comput. Geom. 50(3), 679-699 (2013) · Zbl 1279.52023 · doi:10.1007/s00454-013-9533-x
[21] Grande, F.: On \[k\] k-level matroids: geometry and combinatorics. Ph.D. thesis, Free University of Berlin (2015)
[22] Grande, F., Rué, J.: Many 2-level polytopes from matroids. Discrete Comput. Geom. 54(4), 954-979 (2015) · Zbl 1342.05021 · doi:10.1007/s00454-015-9735-5
[23] Grande, F., Sanyal, R.: Theta rank, levelness, and matroid minors. J. Comb. Theory Ser. B 123, 1-31 (2017) · Zbl 1354.05020 · doi:10.1016/j.jctb.2016.11.002
[24] Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol. 2. Springer, Berlin (1993) · Zbl 0837.05001
[25] Hampe, S., Joswig, M., Benjamin, S.: Algorithms for tight spans and tropical linear spaces (2016). arXiv:1612.03592 · Zbl 1498.05046
[26] Hanner, O.: Intersections of translates of convex bodies. Math. Scand. 4, 65-87 (1956) · Zbl 0070.39302 · doi:10.7146/math.scand.a-10456
[27] Hansen, A.: On a certain class of polytopes associated with independence systems. Math. Scand. 41, 225-241 (1977) · Zbl 0411.05033 · doi:10.7146/math.scand.a-11716
[28] Kaibel, Volker, Pfetsch, Marc E.: Computing the face lattice of a polytope from its vertex-facet incidences. Comput. Geom. 23(3), 281-290 (2002) · Zbl 1015.52010 · doi:10.1016/S0925-7721(02)00103-7
[29] Kalai, G.: The number of faces of centrally-symmetric polytopes. Graphs Comb. 5(1), 389-391 (1989) · Zbl 1168.52303 · doi:10.1007/BF01788696
[30] Kuznetsov, S., Obiedkov, S.: Comparing performance of algorithms for generating concept lattices. J. Exp. Theor. Artif. Intell. 14, 189-216 (2002) · Zbl 1024.68020 · doi:10.1080/09528130210164170
[31] Lovász, L.; Reed, BA (ed.); Sales, CL (ed.), Semidefinite programs and combinatorial optimization, 137-194 (2003), Berlin · Zbl 1040.90032
[32] Lovasz, L., Saks, M.: Lattices, mobius functions and communications complexity. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, Washington, DC, USA, SFCS ’88, pp. 81-90. IEEE Computer Society (1988)
[33] McKay, B.D., Piperno, A.: Practical graph isomorphism, II. J. Symb. Comput. 60, 94-112 (2014) · Zbl 1394.05079 · doi:10.1016/j.jsc.2013.09.003
[34] Moore, E.H.: Introduction to a form of general analysis. Yale University Press, New Haven (1910) · JFM 41.0376.01 · doi:10.1090/coll/002/01
[35] Paffenholz, A.: Faces of Birkhoff polytopes. Electron. J. Comb. 22, 1-67 (2015) · Zbl 1311.52015
[36] Pashkovich, K.: Extended formulations for combinatorial polytopes. Ph.D. thesis, Magdeburg Universität (2012)
[37] Sanyal, R., Werner, A., Ziegler, G.: On Kalai’s conjectures concerning centrally symmetric polytopes. Discrete Comput. Geom. 41(2), 183-198 (2009) · Zbl 1168.52013 · doi:10.1007/s00454-008-9104-8
[38] Siek, J., Allison, C.: Boost 1.63 C++ libraries: Dynamic bitset 1.29.0. (2016) http://www.boost.org/doc/libs/1_63_0/libs/dynamic_bitset/dynamic_bitset.html. Accessed 7 May 2017
[39] Stanley, R.: Decompositions of rational convex polytopes. Ann. Discrete Math. 6, 333-342 (1980) · Zbl 0812.52012 · doi:10.1016/S0167-5060(08)70717-9
[40] Stanley, R.: Two poset polytopes. Discrete Comput. Geom. 1(1), 9-23 (1986) · Zbl 0595.52008 · doi:10.1007/BF02187680
[41] Sullivant, S.: Compressed polytopes and statistical disclosure limitation. Tohoku Math. J. Second Ser. 58(3), 433-445 (2006) · Zbl 1121.52028 · doi:10.2748/tmj/1163775139
[42] Walter, J., Koch, M.: Boost 1.63: Basic linear algebra library (2016) http://www.boost.org/doc/libs/1_63_0/libs/numeric/ublas
[43] Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441-466 (1991) · Zbl 0748.90074 · doi:10.1016/0022-0000(91)90024-Y
[44] Ziegler, G.: Lectures on Polytopes, vol. 152. Springer, Berlin (1995) · Zbl 0823.52002
[45] Ziegler, G.; Kalai, G. (ed.); Ziegler, G. (ed.), Lectures on 0/1-polytopes, No. 29, 1-41 (2000), Birkhäuser · Zbl 0966.52012
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.