×

zbMATH — the first resource for mathematics

Enumeration of 2-level polytopes. (English) Zbl 1394.52008
Bansal, Nikhil (ed.) et al., Algorithms – ESA 2015. 23rd annual European symposium, Patras, Greece, September 14–16, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48349-7/pbk; 978-3-662-48350-3/ebook). Lecture Notes in Computer Science 9294, 191-202 (2015).
Summary: We propose the first algorithm for enumerating all combinatorial types of 2-level polytopes of a given dimension \(d\), and provide complete experimental results for \(d \leqslant 6\). Our approach is based on the notion of a simplicial core, that allows us to reduce the problem to the enumeration of the closed sets of a discrete closure operator, along with some convex hull computations and isomorphism tests.
For the entire collection see [Zbl 1320.68011].

MSC:
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
05A15 Exact enumeration problems, generating functions
52B55 Computational aspects related to convexity
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aichholzer, O.: Extremal properties of 0/1-polytopes of dimension 5. In: Ziegler, G., Kalai, G. (eds.) Polytopes - Combinatorics and Computation, pp. 111–130. Birkhäuser (2000) · Zbl 0966.52011
[2] Akutsu, T.: On determining the congruence of point sets in d dimensions. Computational Geometry 9(4), 247–256 (1998) · Zbl 0894.68156 · doi:10.1016/S0925-7721(97)00010-2
[3] Beyer, S.: Comprehensive perl archive network: Bit-vector-7.4 (2014). http://search.cpan.org/ stbey/Bit-Vector-7.4
[4] Chvátal, V.: On certain polytopes associated with graphs. J. Combinatorial Theory Ser. B 18, 138–154 (1975) · Zbl 0277.05139 · doi:10.1016/0095-8956(75)90041-6
[5] De Loera, J., Rambau, J., Santos, F.: Triangulations. Algorithms and Computation in Mathematics, vol. 25 (2010) · Zbl 1207.52002 · doi:10.1007/978-3-642-12971-1
[6] Ganter, B., Reuter, K.: Finding all closed sets: A general approach. Order 8(3), 283–290 (1991) (English) · Zbl 0754.06003
[7] Gawrilow, E., Joswig, M.: Polymake: an approach to modular software design in computational geometry. In: International Symposium on Computational Geometry (SOCG), pp. 222–231. ACM Press (2001) · Zbl 1375.68136 · doi:10.1145/378583.378673
[8] Gouveia, J., Parrilo, P., Thomas, R.: Theta bodies for polynomial ideals. SIAM Journal on Optimization 20(4), 2097–2118 (2010) · Zbl 1213.90190 · doi:10.1137/090746525
[9] Gouveia, J., Robinson, R., Thomas, R.: Polytopes of minimum positive semidefinite rank. Discrete & Computational Geometry 50(3), 679–699 (2013) · Zbl 1279.52023 · doi:10.1007/s00454-013-9533-x
[10] Grande, F., Sanyal, R.: Theta rank, levelness, and matroid minors, arXiv preprint, arXiv:1408.1262 (2014) · Zbl 1354.05020
[11] Haase, C.: Lattice polytopes and unimodular triangulations, Ph.D. thesis, Technical University of Berlin (2000) · Zbl 1066.14508
[12] Hanner, O.: Intersections of translates of convex bodies. Mathematica Scandinavica 4, 65–87 (1956) · Zbl 0070.39302 · doi:10.7146/math.scand.a-10456
[13] Hansen, A.: On a certain class of polytopes associated with independence systems. Mathematica Scandinavica 41, 225–241 (1977) · Zbl 0411.05033 · doi:10.7146/math.scand.a-11716
[14] Kalai, G.: The number of faces of centrally-symmetric polytopes. Graphs and Combinatorics 5(1), 389–391 (1989) · Zbl 1168.52303 · doi:10.1007/BF01788696
[15] Kuznetsov, S., Obiedkov, S.: Comparing performance of algorithms for generating concept lattices. Journal of Experimental and Theoretical Artificial Intelligence 14, 189–216 (2002) · Zbl 1024.68020 · doi:10.1080/09528130210164170
[16] Paffenholz, A.: Faces of Birkhoff polytopes. Electronic Journal of Combinatorics 22 (2015) · Zbl 1311.52015
[17] Sanyal, R., Werner, A., Ziegler, G.: On Kalai’s conjectures concerning centrally symmetric polytopes. Discrete & Computational Geometry 41(2), 183–198 (2009) · Zbl 1168.52013 · doi:10.1007/s00454-008-9104-8
[18] Stanley, R.: Decompositions of rational convex polytopes. Annals of Discrete Mathematics, 333–342 (1980) · Zbl 0812.52012 · doi:10.1016/S0167-5060(08)70717-9
[19] Stanley, R.: Two poset polytopes. Discrete & Computational Geometry 1(1), 9–23 (1986) · Zbl 0595.52008 · doi:10.1007/BF02187680
[20] Sullivant, S.: Compressed polytopes and statistical disclosure limitation. Tohoku Mathematical Journal, Second Series 58(3), 433–445 (2006) · Zbl 1121.52028 · doi:10.2748/tmj/1163775139
[21] Ziegler, G.: Lectures on polytopes, vol. 152, Springer Science & Business Media (1995) · Zbl 0823.52002 · doi:10.1007/978-1-4613-8431-1
[22] Ziegler, G.: Lectures on 0/1-polytopes. In: Kalai, G., Ziegler, G. (eds.) Polytopes - Combinatorics and Computation. DMV Seminar, vol. 29, pp. 1–41. Springer, Birkhäuser, Basel (2000) · Zbl 0966.52012 · doi:10.1007/978-3-0348-8438-9_1
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.