This article is cited in
5 papers
$k$-neighborly faces of the Boolean quadric polytopes
A. N. Maksimenko P. G. Demidov Yaroslavl State University, Yaroslavl, Russia
Abstract:
The Boolean quadric polytope (or correlation polytope) is the convex hull
$$
\operatorname{BQP}(n)=\operatorname{conv}\{x=(x_{ij})\in\{0,1\}^{n(n+1)/2}\mid x_{ij}=x_{ii}x_{jj},\ 1\le i\le j\le n\}.
$$
The number of its vertices is
$2^n$, i.e., superpolynomial in the dimension
$d=n(n+1)/2$. In 1992 M. Deza, M. Laurent, and S. Poljak proved that
$\operatorname{BQP}(n)$ is
$3$-neighborly, i.e., every three vertices of
$\operatorname{BQP}(n)$ form a face of this polytope. By analogy with the Boolean quadric polytopes, we consider Boolean
$p$-power polytopes
$\operatorname{BQP}(n,p)$. For
$p=2$,
$\operatorname{BQP}(n,p)=\operatorname{BQP}(n)$. For
$p=1$,
$\operatorname{BQP}(n,p)$ is
$n$-dimensional
$0/1$-cube. It is shown that
$\operatorname{BQP}(n,p)$ is
$s$-neighborly for
$s\le p+\lfloor p/2\rfloor$. For
$k\ge2m$,
$m\in\mathbb N$, we prove that the polytope
$\operatorname{BQP}(k,2m)$ is linearly isomorphic to a face of
$\operatorname{BQP}(n)$ for some
$n=\Theta\left(\binom km\right)$. Hence, for every fixed
$s\le3\lfloor\log_2 n/2\rfloor$,
$\operatorname{BQP}(n)$ has
$s$-neighborly face with superpolynomial number
$2^{\Theta(n^{1/\lceil s/3\rceil})}$ of vertices.
UDC:
519.854.33+
514.172.45
Fulltext:
PDF file (159 kB)