6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Jul 12, 2012 at 10:04
  • $\begingroup$ I mean pairwise non-orthogonal. Sorry for the confusion. $\endgroup$ Jul 12, 2012 at 10:08
  • 1
    $\begingroup$ Your question is very related to Borsuk's conjecture, en.wikipedia.org/wiki/Borsuk%27s_conjecture (I am sure you know it, but want to say just in case not.) $\endgroup$ Jul 12, 2012 at 12:44
  • $\begingroup$ Thanks for pointing that out. I must admit that I was not aware of it. $\endgroup$ Jul 12, 2012 at 14:19
  • $\begingroup$ The statement is of course true for $d=n$. It seems more elegant to include that case. $\endgroup$
    – Will Sawin
    Jul 12, 2012 at 15:03

1 Answer 1

5
$\begingroup$

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

Imagine that this cube sits in a coordinate hyperplane $x_1=s$ 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 a right choice of $s$, you get a counterexample to your statement.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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