Bounds on the number of 2-level polytopes, cones, and configurations

DOI10.1007/S00454-020-00181-4MaRDI QIDQ2664102zbMATH OpenOpenAlexFDO

Authors Samuel Fiorini, Marco Macchia, Kanstantsin Pashkovich

Publication date 20 April 2021

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.06011

zbMATH Keywords

2-level polytopesasymptotic enumerationcommunication complexityslack matrix

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial complexity of geometric structures (52C45)

Abstract: We prove an upper bound of the form $2^{O(d^{2}mathrmpolylog,d)}$ on the number of affine (resp. linear) equivalence classes of, by increasing order of generality, 2-level d-polytopes, d-cones and d-configurations. This in particular answers positively a conjecture of Bohn et al. on 2-level polytopes. We obtain our upper bound by relating affine (resp. linear) equivalence classes of 2-level d-polytopes, d-cones and d-configurations to faces of the correlation cone. We complement this with a $2^{Omega(d^2)}$ lower bound, by estimating the number of nonequivalent stable set polytopes of bipartite graphs.

Recommendations

• Many 2-level polytopes from matroids
• scientific article; zbMATH DE number 3931029

Cites work

• Communication Complexity
• Communication complexity and combinatorial lattice theory
• Compressed polytopes and statistical disclosure limitation
• Expressing combinatorial optimization problems by linear programs
• Four-dimensional polytopes of minimum positive semidefinite rank
• Geometry of cuts and metrics
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• scientific article; zbMATH DE number 3095897 (Why is no real title available?)
• Intersections of translates of convex bodies
• Lower bounds in communication complexity
• Many 2-level polytopes from matroids
• On certain polytopes associated with graphs
• Polytopes of minimum positive semidefinite rank
• Theta bodies for polynomial ideals
• Two poset polytopes
• Which nonnegative matrices are slack matrices?

Cited in

(2)

• Binary scalar products
• Stability for binary scalar products

Describes a project that uses

Uses Software

• 2L_enum

This page was built for publication: Bounds on the number of 2-level polytopes, cones, and configurations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2664102)