A Weak Form of Borsuk's Conjecture - MathOverflow

A Weak Form of Borsuk's Conjecture

2012-07-23T15:13:46Z

Problem: Let P be a d-dimensional polytope with n facets. Is it always true that P can be covered by n sets of smaller diameter?

Background and motivation

The Borsuk conjecture (disproved in 1993) asserted that every set of diameter 1 in $R^d$ can be covered by $d+1$ sets of smaller diameter. Since every $d$-polyope has at least $d+1$ facets our proposal is indeed a weaker statement.

My motivation for this question comes from the paper Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf. The paper solves an old conjecture of Yannakakis about projections of polytopes and shows, in particular, that the $n$-dimensional cut polytope cannot be described as a projection of a polytope with only a polynomial number (in $n$) of facets.

Another proof of this result of Fioroni et als. (regarding cuts polytopes) will follow from an affirmative answer of a slight strengthening of the proposed problem:

Problem: If $P$ is a $d$-polytope of diameter 1 with $n$ facets then $P$ can be covered by $n$ sets of diameter $1-\epsilon$ wher $\epsilon$ may depend on $n$ (but not on $P$.)

Answer by Dima Pasechnik for A Weak Form of Borsuk's Conjecture

2012-10-20T11:43:09Z

This is not an answer, but rather few related comments/questions, which are hard to fit into "proper" comments.

There are polytopes $P$ which are very easy to cover, e.g. take $P$ a regular $d$-dimensional hypercube (so $n=2d$). It can be covered by just 2 bodies of smaller diameter: take a hyperplane parallel to a pair of opposite facets, right in the middle of them. It cuts $P$ into two halves, of smaller diameter, as it cuts each "longest diagonal" of $P$.

So the 1st question: what are examples for which more than 2 (variations: more than a constant, or more than $d+1$) parts are needed?

The above observation for the hypercube also seems to indicate that if one has just one longest diagonal, a similar argument works: just take a hyperplane cutting it, orthogonally, in the middle. (And thus almost all polytopes need just 2 parts). This says that the set of the longest diagonals is something to look into. One might try to argue that cutting them all with few hyperplanes is possible.

Thus, 2nd question: can one assume that each vertex has at least one longest diagonal on it? It seems that it might suffice to look at the convex hull of vertices on a least one longest diagonal.