Suppose $H_1,\ldots,H_{2n}$ are open hemispheres which cover $S^{n-1}$ with the property that removing any one of them leaves $S^{n-1}$ uncovered. Is it necessarily the case that the hemispheres can be grouped into antipodal pairs? That is, possibly after reordering we have $H_i=-H_{i+1}$ for $i=1,3,5,\ldots,2n-1$?

Another way to phrase this question is as follows: Suppose there are $2n$ points in $S^{n-1}$ with the property that the origin lies in the interior of their convex hull, but the origin does not lie in the interior of the convex hull of any proper subset of the points. Is it necessarily the case that the points can be grouped into antipodal pairs?

  • 4
    $\begingroup$ This is true for $S^1$ ($2n=4$). Why the downvotes? $\endgroup$ – YCor Feb 27 '16 at 1:13
  • $\begingroup$ Good problem: After trying a lot of "clever" things to try to construct a counterexample for $n=3$, I am starting to see that the "removing any clause frustrates a lot of plausible coverings. $\endgroup$ – Mark Fischler Feb 27 '16 at 1:55
  • $\begingroup$ Is there even a counterexample, where the points are not the points of a cross polytope? $\endgroup$ – Moritz Firsching Feb 27 '16 at 9:04

It looks so. We start with inductive proof of

Steinitz Theorem. Let $A$ be a finite set of rays starting from the origin in $\mathbb{R}^d$. Assume that positive span of these rays is the whole $\mathbb{R}^d$. Then there exists a subset of at most $2d$ rays from $A$ with the same property.

Proof. Induction in $d$. Base $d=1$ is clear. Induction step. Choose minimal $k$ such that some $k$ vectors $a_1,\dots,a_k$ which generate rays from $A$ are linearly dependent with positive coefficients: $\sum t_i a_i=0$, $t_i>0$. Then $0$ lies in interior of a $(k-1)$-dimensional simplex with vertices $a_1,\dots,a_k$. Let $X={\rm span}\,(a_1,\dots,a_k)$, $\dim X=k-1$. Factor everything modulo $X$, we get a space of dimension $d-k+1$, 0 lies in an interior of a convex hull of the image of $A\setminus {\mathbb R}_+\cdot \{a_1,\dots,a_k\}$, and it suffices to use $2(d-k+1)$ rays by induction proposition, add to them rays generated by $a_1,\dots,a_k$ to get totally at most $2(d-k+1)+k=2d+(2-k)\leqslant 2d$ rays.

If on the first step it was $k>2$, we get improved bound $2d-1$ on the number of used rays. If $k=2$, then we find a pair of opposite rays. If we proceed by induction proving your statement, we may think that two rays have generators $\pm e_d$ and generators of others are partitioned onto pairs $(x_k,\alpha_d)$, $(-x_k,\beta_d)$ for some $x_1,\dots,x_{2d-2}\in \mathbb{R}^{d-1}$. If $\alpha_d\ne \beta_d$, then considering above 4 rays, which lie in a 2-plane, it is easy to see that the whole 2-plane is generated by some three of them, so safely remove one ray.

  • 1
    $\begingroup$ The fact you are proving in the first part is Steinitz' theorem; see, e.g., csclub.uwaterloo.ca/~jy2wong/jenerated/blog/… $\endgroup$ – Ilya Bogdanov Feb 27 '16 at 13:43
  • $\begingroup$ @IlyaBogdanov thank you, I have to mention this. $\endgroup$ – Fedor Petrov Feb 27 '16 at 14:20
  • $\begingroup$ Very nice. It is interesting that Steinitz' bound can be refined from $2d$ to $2d-k+2$, where $k-1$ is the dimension of the largest simplex whose vertices lie in the given rays and whose relative interior contains the origin. $\endgroup$ – Marcel Celaya Mar 1 '16 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.