FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA

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

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

Last modified: January 7, 2014