21
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ For readers' convenience: en.wikipedia.org/wiki/Borsuk%27s_conjecture $\endgroup$
    – Mark Meckes
    Commented Jul 23, 2012 at 18:14
  • 3
    $\begingroup$ 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. $\endgroup$
    – Vidit Nanda
    Commented Jul 23, 2012 at 19:06
  • $\begingroup$ 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. $\endgroup$
    – Gil Kalai
    Commented Jul 29, 2012 at 0:48
  • $\begingroup$ Dear Prof. Kalai, how many faces in your example? $\endgroup$
    – Arseniy Akopyan
    Commented Jul 30, 2012 at 8:06
  • 2
    $\begingroup$ 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... $\endgroup$
    – Vidit Nanda
    Commented Jul 31, 2012 at 23:59

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .