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.
$\begingroup$
$\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$– Geoff RobinsonJul 12, 2012 at 10:04
-
$\begingroup$ I mean pairwise non-orthogonal. Sorry for the confusion. $\endgroup$– Pawan AuroraJul 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$– Anton PetruninJul 12, 2012 at 12:44
-
$\begingroup$ Thanks for pointing that out. I must admit that I was not aware of it. $\endgroup$– Pawan AuroraJul 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 SawinJul 12, 2012 at 15:03
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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.