I PRIKLADNAYA MATEMATIKA
(FUNDAMENTAL AND APPLIED MATHEMATICS)
2013, VOLUME 18, NUMBER 2, PAGES 95-103
-neighborly faces of the Boolean quadric
A. N. Maksimenko
View as HTML
View as gif image
The Boolean quadric polytope (or correlation polytope) is the convex
The number of its vertices is , i.e.,
superpolynomial in the dimension .
In 1992 M. Deza, M. Laurent, and S. Poljak proved that
i.e., every three vertices of form a face of
By analogy with the Boolean quadric polytopes, we consider Boolean
It is shown that is -neighborly for
For , , we prove that the polytope is linearly
isomorphic to a face of for some .
Hence, for every fixed , has -neighborly face with
superpolynomial number of vertices.
Last modified: January 7, 2014