RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Journal history Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Fundam. Prikl. Mat.: Year: Volume: Issue: Page: Find

 Fundam. Prikl. Mat., 2013, Volume 18, Issue 2, Pages 95–103 (Mi fpm1501)

$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(\binom km)$. 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.

Full text: PDF file (159 kB)
References: PDF file   HTML file

English version:
Journal of Mathematical Sciences (New York), 2014, 203:6, 816–822

Bibliographic databases:

UDC: 519.854.33+514.172.45

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

Citation in format AMSBIB
\Bibitem{Mak13} \by A.~N.~Maksimenko \paper $k$-neighborly faces of the Boolean quadric polytopes \jour Fundam. Prikl. Mat. \yr 2013 \vol 18 \issue 2 \pages 95--103 \mathnet{http://mi.mathnet.ru/fpm1501} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3431787} \transl \jour J. Math. Sci. \yr 2014 \vol 203 \issue 6 \pages 816--822 \crossref{https://doi.org/10.1007/s10958-014-2171-x} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84922076392} 

• http://mi.mathnet.ru/eng/fpm1501
• http://mi.mathnet.ru/eng/fpm/v18/i2/p95

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. A. V. Seliverstov, “Mnogogranniki i svyaznye podgrafy”, Diskretn. analiz i issled. oper., 21:3 (2014), 82–86
2. A. N. Maksimenko, “Kharakteristiki slozhnosti: klikovoe chislo grafa mnogogrannika i chislo pryamougolnogo pokrytiya”, Model. i analiz inform. sistem, 21:5 (2014), 116–130
3. A. N. Maksimenko, “A special role of Boolean quadratic polytopes among other combinatorial polytopes”, Model. i analiz inform. sistem, 23:1 (2016), 23–40
4. A. N. Maksimenko, “Bulev kvadratichnyi mnogogrannik yavlyaetsya granyu mnogogrannika lineinykh poryadkov”, Sib. elektron. matem. izv., 14 (2017), 640–646
•  Number of views: This page: 205 Full text: 52 References: 31 First page: 1