Extremal properties of \(0/1\)-polytopes (Q1356085): Difference between revisions

The authors study \(d\)-dimensional 0/1-polytopes and their 2-dimensional projections. They establish that the maximal number \(f(d)\) of facets of a 0/1-polytope satisfies the inequalities: \[ \begin{aligned} f(d) \geq(26 286)^{\lfloor d/10 \rfloor} 2^{d\bmod 10} \quad & (d\geq 0) \\ f(d) \leq d!-(d-1)! +2(d-1) \quad & (d\geq 3) \end{aligned} \] They also establish that the maximal number \(H_{sh} ({\mathcal P}_d)\) of extremal vertices of a two-dimensional shadow of a \(d\)-dimensional 0/1-polytope satisfies the inequalities \[ H_{sh} ({\mathcal P}_d) \geq 2^{\bigl \lfloor (d+ 5)/3 \bigr \rfloor} \quad (d\geq 4) \] \[ H_{sh} ({\mathcal P}_d) \geq 2(1+ \sqrt 3) 2^{d (\log 3/ \log 6)}. \]