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

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₂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