4
$\begingroup$

Let $I^n$ be the set of vertices of the unit cube of dimension $n$ with the standard ($l_1$) distance. Then any set of vertices in $I^n$ consisting of vertices at pairwise distance $n$ is the pair of ends of a large diagonal. There are $2^{n-1}$ of those. Thus the following property holds

  • If we color $I^n$ in fewer than $2^{n-1}$ colors, then at least for one color $i$ the set of vertices of color $i$ is $n$-distance connected, i.e. any two vertices of color $i$ are connected by a sequence of vertices $v_0,...,v_m$ such that the distance between $v_j$ and $v_{j+1}$ is less than $n$, $j=1,...,m-1$.

Question Is it true that if we color $I^{n+1}$ in fewer than $2^{n-1}$ colors, then at least for one color $i$ the set of vertices of color $i$ is $n$-distance connected (assume $n\gg 1$)?

$\endgroup$
12
  • $\begingroup$ sorry, shouldn't it be "at pairwise distance $n$"? $\endgroup$ Apr 19, 2012 at 19:27
  • $\begingroup$ Why the distance between ends of diagonal equals $n-1$, not $n$? $\endgroup$ Apr 19, 2012 at 19:28
  • $\begingroup$ These were misprints. $\endgroup$
    – user6976
    Apr 19, 2012 at 19:34
  • $\begingroup$ It is quite possible that each color will consist of one vertex $x$ and several vertices on distance exactly $n$ from $x$. Even if the number of colors is about $2^n/n$ $\endgroup$ Apr 19, 2012 at 20:03
  • $\begingroup$ I second Fedor's second (as seen at this writing) comment. Gerhard "Motion To Adjourn Always Proper" Paseman, 2012.04.19 $\endgroup$ Apr 19, 2012 at 20:12

1 Answer 1

7
$\begingroup$

I work with $I_n$ instead $I_{n+1}$. Consider pairs of opposite vertices. There are $2^n$ such pairs. We want to find $K=O(2^n/n)$ such pairs (call them nice) so that for any other pair $(u,u')$ there is a nice pair $(v,v')$ with distance $d(u,v)=1$. Then we may color all vertices in at most $2K$ colors so that each color consists either of two opposite vertices, or of one vertex and few vertices on distance $n$ from it. Indeed, enumerate all nice pairs $(u_1,u_1')$, $(u_2,u_2'),\dots$. On $k$-th step we consider the (yet uncolored) nice pair $(u_k,u_k')$ and consider all uncolored and not nice pairs on distance 1 from it. If there is at least one such pair, we use two new colors, one for $u_k$ and uncolored and not nice points close to $u_k'$ and viceversa. If there are no such pairs, use one color for $(u_k,u_k')$. Then proceed.

Now must explain how we find $K$ such pairs. Let's think about $I_n$ as about vector space $\mathbb{F}_2^n$. Consider $m$ independent linear functionals $f_1,\dots,f_m$ on $I_n$ and define as nice all points for which all of them vanish (plus all opposite points, since pairs are nice, not points). What is condition for our linear functionals under which for any $x\in I_n$ there exists $y\in I_n$ on distance at most 1 from $x$ with $f_1(y)=\dots=f_m(y)=0$? It is the following condition: for any vector $(c_1,\dots,c_m)\in \mathbb{F}_2^m$ there exists a unit basic vector $e=(0,\dots,0,1,0,\dots,0)$ with prescribed values $f_i(e)=c_i,1\leq i\leq m$. This is possible provided that $2^m\leq n$, because we may define values of functionals on basic vector as we wish, and we just need enough basic vector for all patterns $(c_1,\dots,c_m)$. So, we get exactly $2^{n-m}$ points, on which all functionals $f_1,\dots,f_m$ vanish, hence at most $2^{n+1-m}$ pairs.

$\endgroup$
1

Your Answer

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