# A Weak Form of Borsuk's Conjecture

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$.)

-
For readers' convenience: en.wikipedia.org/wiki/Borsuk%27s_conjecture –  Mark Meckes Jul 23 '12 at 18:14
Completely unverified heuristic follows: if the number of vertices in the boundary of $P$ is smaller than $n$, we can immediately use the intersections of $P$ with the Voronoi cells associated to the vertex set as a covering. If the vertex set in the boundary has cardinality larger than $n$, then use the Voronoi cells arising from the $n$barycenters of the facets. This works for all the low dimensional polytopes I have drawn so far, but since the counterexamples to Borsuk's conjecture live in ~300 dimensions, this could fail miserably. –  Vidit Nanda Jul 23 '12 at 19:06
Dear Vel, This is a nice idea but I doubt if it works even in low dimensions. Namely the Voronoi cells corresponding to a facet may include this entire facet. –  Gil Kalai Jul 29 '12 at 0:48
Dear Prof. Kalai, how many faces in your example? –  akopyan Jul 30 '12 at 8:06
Professor Kalai: the "worst case" for that Voronoi idea is a simplex on n equidistant points, since all facets in sight have the same diameter as the original simplex. But in this case, we can just use the n vertices for generating the Voronoi diagram and no facet lies in the same Voronoi cell. Like I said before, it is a silly heuristic, but I can't seem to create a counterexample... –  Vidit Nanda Jul 31 '12 at 23:59

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?