$k$-neighborly faces of the Boolean quadric polytopes

A. N. Maksimenko

Fundamentalʹnaâ i prikladnaâ matematika, Tome 18 (2013) no. 2, pp. 95-103.

Résumé

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.

Bibliographie

[1] Barvinok A. I., Vershik A. M., “Vypuklye obolochki orbit predstavlenii konechnykh grupp i kombinatornaya optimizatsiya”, Funkts. analiz i ego pril., 22:3 (1988), 66–67 | MR | Zbl

[2] Bondarenko V. A., Brodskii A. G., “O sluchainykh $2$-smezhnostnykh $0/1$-mnogogrannikakh”, Diskret. mat., 20:1 (2008), 64–69 | DOI | MR | Zbl

[3] Maksimenko A. N., “Mnogogranniki zadachi o vypolnimosti yavlyayutsya granyami mnogogrannika zadachi kommivoyazhëra”, Diskret. analiz i issled. oper., 18:3 (2011), 76–83 | MR | Zbl

[4] Maksimenko A. N., “Ob universalnykh svoistvakh mnogogrannika razrezov”, Problemy teoreticheskoi kibernetiki, Mater. XVI mezhdunar. konf., Izd-vo Nizhegorodskogo gos. un-ta, 2011, 294–296

[5] Maksimenko A. N., “Ob affinnoi svodimosti kombinatornykh mnogogrannikov”, Dokl. RAN, 443:6 (2012), 661–663 | MR | Zbl

[6] Billera L. J., Sarangarajan A., “All $0$-$1$ polytopes are traveling salesman polytopes”, Combinatorica, 16:2 (1996), 175–188 | DOI | MR | Zbl

[7] Christof T., Reinelt G., “Decomposition and parallelization techniques for enumerating the facets of combinatorial polytopes”, Int. J. Comput. Geom. Appl., 11:4 (2001), 423–437 | DOI | MR | Zbl

[8] Deza M. M., Laurent M., Geometry of Cuts and Metrics, Springer, Berlin, 1997 | MR | Zbl

[9] Deza M. M., Laurent M., Poljak S., “The cut cone. III: On the role of triangle facets”, Graphs Combin., 8:2 (1992), 125–142 | DOI | MR | Zbl

[10] Fiorini S., Massar S., Pokutta S., Tiwary H. R., de Wolf R., Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds, 2011, arXiv: 1111.0837v3

[11] Gillmann R., $0/1$-Polytopes: Typical and Extremal Properties, PhD Thesis, TU Berlin, 2006 | Zbl

[12] Henk M., Richter-Gebert J., Ziegler G. M., “Basic properties of convex polytopes”, Handbook of Discrete and Computational Geometry, eds. J. E. Goodman, J. O'Rourke, Chapman and Hall/CRC, 2004, 355–382 | MR

[13] Onn S., “Geometry, complexity, and combinatorics of permutation polytopes”, J. Combin. Theory Ser. A, 64 (1993), 31–49 | DOI | MR | Zbl

[14] De Simone C., “The cut polytope and the Boolean quadric polytope”, Discrete Math., 79 (1990), 71–75 | DOI | MR | Zbl

[15] http://www.iwr.uni-heidelberg.de/groups/comopt/software/SMAPO/