|
Fundamentalnaya i Prikladnaya Matematika, 2013, Volume 18, Issue 2, Pages 95–103
(Mi fpm1501)
|
|
|
|
This article is cited in 5 scientific papers (total 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.
Citation:
A. N. Maksimenko, “$k$-neighborly faces of the Boolean quadric polytopes”, Fundam. Prikl. Mat., 18:2 (2013), 95–103; J. Math. Sci., 203:6 (2014), 816–822
Linking options:
https://www.mathnet.ru/eng/fpm1501 https://www.mathnet.ru/eng/fpm/v18/i2/p95
|
|