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

2018/06/15 by Fiorini, Samuel, Macchia, Marco, Pashkovich, Kanstantsin
#05A16 #52C45 #90C57 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1806.06011

Abstract

We prove an upper bound of the form 2^{O(d2 polylog 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^Ω(d2) lower bound, by estimating the number of nonequivalent stable set polytopes of bipartite graphs.

Related

• On 2-level polytopes arising in combinatorial settings
• Many 2-level polytopes from matroids
• Enumeration of 2-level polytopes
• Stability for binary scalar products
• A lower bound theorem for d-polytopes with 2d+2 vertices