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$
  • $\begingroup$ sorry, shouldn't it be "at pairwise distance $n$"? $\endgroup$ – Pietro Majer Apr 19 '12 at 19:27
  • $\begingroup$ Why the distance between ends of diagonal equals $n-1$, not $n$? $\endgroup$ – Fedor Petrov Apr 19 '12 at 19:28
  • $\begingroup$ These were misprints. $\endgroup$ – Mark Sapir Apr 19 '12 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$ – Fedor Petrov Apr 19 '12 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$ – Gerhard Paseman Apr 19 '12 at 20:12
8
$\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$

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.