MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given $n$ unit vectors in $\mathbb{R}^n$ s.t. $0 \leq u\cdot v<1$ for all pair of distinct vectors $u,v$. These vectors span a $d$-dimensional subspace s.t. $d< n$. We conjecture that it is possible to partition the $n$ vectors into $d$ groups such that all the vectors within the same group are pairwise non-orthogonal. It trivially holds when $d\in\{1,2,n-1,n-2\}$. However, we have not been able to show for general $d$. Does the conjecture hold for any $d< n$? If yes, how to prove it? Any thoughts/hints would be appreciated. Thanks in advance.

share|cite|improve this question
By "mutually non-orthogonal" do you mean "pairwise non-orthogonal" for the vectors in the $d$ sets, or do you mean that no vector in the set is orthogonal to ALL of the others? – Geoff Robinson Jul 12 '12 at 10:04
I mean pairwise non-orthogonal. Sorry for the confusion. – Pawan Aurora Jul 12 '12 at 10:08
Your question is very related to Borsuk's conjecture, (I am sure you know it, but want to say just in case not.) – Anton Petrunin Jul 12 '12 at 12:44
Thanks for pointing that out. I must admit that I was not aware of it. – Pawan Aurora Jul 12 '12 at 14:19
The statement is of course true for $d=n$. It seems more elegant to include that case. – Will Sawin Jul 12 '12 at 15:03
up vote 3 down vote accepted

Kahn--Kalai' counterexample to Borsuk's conjecture is a collection of vertices of unit cube.

Think about this cube as it siitting in an affine hyperplane of $\mathbb R^{n+1}$, so that the origin projects to the center of the cube. Project this cube centrally to the unit sphere. For right choice of parameter you get a counterexample to your statement.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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