Abstract
A (convex) polytope is said to be 2-level if for every facet-defining direction of hyperplanes, its vertices can be covered with two hyperplanes of that direction. These polytopes are motivated by questions, e.g., in combinatorial optimization and communication complexity. We study 2-level polytopes with one prescribed facet. Based on new general findings about the structure of 2-level polytopes, we give a complete characterization of the 2-level polytopes with some facet isomorphic to a sequentially Hanner polytope, and improve the enumeration algorithm of Bohn et al. (ESA 2015). We obtain, for the first time, the complete list of d-dimensional 2-level polytopes up to affine equivalence for dimension \(d = 7\). As it turns out, geometric constructions that we call suspensions play a prominent role in both our theoretical and experimental results. This yields exciting new research questions on 2-level polytopes, which we state in the paper.
We acknowledge support from ERC grant FOREFRONT (grant agreement no. 615640) funded by the European Research Council under the EU’s 7th Framework Programme (FP7/2007-2013).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
While in general two polytopes can be combinatorially equivalent without being affinely equivalent, for 2-level polytopes these two notions coincide [2]. We simply say that two 2-level polytopes are isomorphic whenever they are combinatorially (or affinely) equivalent.
- 2.
The computed polytopes in polymake format and more experimental results are available online http://homepages.ulb.ac.be/~vfisikop/data/2-level.html.
- 3.
Hydra balanced cluster: http://cc.ulb.ac.be/hpc/hydra.php.
References
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, Basel (2000)
Bohn, A., Faenza, Y., Fiorini, S., Fisikopoulos, V., Macchia, M., Pashkovich, K.: Enumeration of 2-level polytopes. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 191–202. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48350-3_17
Chvátal, V.: On certain polytopes associated with graphs. J. Comb. Theory Ser. B 18, 138–154 (1975)
Fukuda, K., Miyata, H., Moriyama, S.: Complete enumeration of small realizable oriented matroids. Discrete Comput. Geom. 49(2), 359–381 (2013)
Ganter, B., Reuter, K.: Finding all closed sets: a general approach. Order 8(3), 283–290 (1991)
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)
Gouveia, J., Parrilo, P., Thomas, R.: Theta bodies for polynomial ideals. SIAM J. Optim. 20(4), 2097–2118 (2010)
Gouveia, J., Pashkovich, K., Robinson, R.Z., Thomas, R.R.: Four dimensional polytopes of minimum positive semidefinite rank (2015)
Gouveia, J., Robinson, R., Thomas, R.: Polytopes of minimum positive semidefinite rank. Discrete Comput. Geom. 50(3), 679–699 (2013)
Grande, F.: On \(k\)-level matroids: geometry and combinatorics. Ph.D. thesis, Free University of Berlin (2015)
Grande, F., Rué, J.: Many 2-level polytopes from matroids. Discrete Comput. Geom. 54(4), 954–979 (2015)
Grande, F., Sanyal, R.: Theta rank, levelness, matroid minors. arXiv preprint (2014). arXiv:1408.1262
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol. 2. Springer, Heidelberg (1988)
Hanner, O.: Intersections of translates of convex bodies. Mathematica Scandinavica 4, 65–87 (1956)
Hansen, A.: On a certain class of polytopes associated with independence systems. Mathematica Scandinavica 41, 225–241 (1977)
Kalai, G.: The number of faces of centrally-symmetric polytopes. Graphs Comb. 5(1), 389–391 (1989)
Lovász, L.: Semidefinite programs and combinatorial optimization. In: Reed, B.A., Sales, C.L. (eds.) Recent Advances in Algorithms and Combinatorics. CMS Books in Mathematics, pp. 137–194. Springer, Heidelberg (2003)
Lovász, L., Saks, M.: Lattices, mobius functions and communications complexity. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, SFCS 1988, pp. 81–90. IEEE Computer Society, Washington (1988)
Mahler, K.: Ein übertragungsprinzip für konvexe körper. Časopis Pěst. Mat. Fys. 68, 93–102 (1939)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)
Stanley, R.: Two poset polytopes. Discrete Comput. Geom. 1(1), 9–23 (1986)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Fiorini, S., Fisikopoulos, V., Macchia, M. (2016). Two-Level Polytopes with a Prescribed Facet. In: Cerulli, R., Fujishige, S., Mahjoub, A. (eds) Combinatorial Optimization. ISCO 2016. Lecture Notes in Computer Science(), vol 9849. Springer, Cham. https://doi.org/10.1007/978-3-319-45587-7_25
Download citation
DOI: https://doi.org/10.1007/978-3-319-45587-7_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-45586-0
Online ISBN: 978-3-319-45587-7
eBook Packages: Computer ScienceComputer Science (R0)