(FUNDAMENTAL AND APPLIED MATHEMATICS)

2013, VOLUME 18, NUMBER 2, PAGES 95-103

## $k$-neighborly faces of the Boolean quadric polytopes

A. N. Maksimenko

Abstract

View as HTML     View as gif image

The Boolean quadric polytope (or correlation polytope) is the convex hull

$BQP\left(n\right) = conv\left\{x = \left(x$ij) Î {0,1}n(n+1)/2 | xij = xiixjj, 1 £ i £ j £ n}.

The number of its vertices is $2n$, i.e., superpolynomial in the dimension $d = n\left(n+1\right)/2$. In 1992 M. Deza, M. Laurent, and S. Poljak proved that $BQP\left(n\right)$ is $3$-neighborly, i.e., every three vertices of $BQP\left(n\right)$ form a face of this polytope. By analogy with the Boolean quadric polytopes, we consider Boolean $p$-power polytopes $BQP\left(n,p\right)$. For $p = 2$, $BQP\left(n,p\right) = BQP\left(n\right)$. For $p = 1$, $BQP\left(n,p\right)$ is $n$-dimensional $0/1$-cube. It is shown that $BQP\left(n,p\right)$ is $s$-neighborly for $s$£ p+ ëp/2û. For $k$³ 2m, $m$Î N, we prove that the polytope $BQP\left(k,2m\right)$ is linearly isomorphic to a face of $BQP\left(n\right)$ for some $n = \Theta\left(\binom\left\{k\right\}\left\{m\right\}\right)$. Hence, for every fixed $s$£ 3 ëlog2n/2û, $BQP\left(n\right)$ has $s$-neighborly face with superpolynomial number $2^\left\{\Theta \left( n^\left\{1 / \lceil s/3\rceil \right\}\right)\right\}$ of vertices.

Location: http://mech.math.msu.su/~fpm/eng/k13/k132/k13207h.htm