Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to injectively map the vertices of a complete binary tree, $T_d$, which I denote by the binary sequences of length at most $d$, into the hypercube, $C_n$, whose vertices I denote by the binary sequences of length $n$, such that if $x$ and $xb$ (where $b$ is a bit) are two adjacent vertices of $T_d$, then for their images, $f(x)$ and $f(xb)$, it holds that $f(xb)$ has more 1's than $f(x)$ and it has a $1$ everywhere where $f(x)$ has a one. So e.g., $01$ and $011$ might be mapped to $100$ and $101$ or even to $100$ and $111$. (So I do not need that they are adjacent in $C_n$.)

Our goal is to find the smallest $n$ for which such an embedding is possible. It seems like a natural generalization of a very well studied problem (at least if we suppose that the images are adjacent in $C_n$, which should not make a difference in the asymptotics). Has anyone every heard of this problem? Do you think it's possible to apply some variant of the Lovasz Local Lemma?

I conjecture that $n\approx 1.29d$ but I could only prove $1.29d\le n \le 1.38d$. The lower bound follows from the simple observation that we need $\sum_{i\ge d} {n\choose i}\ge 2^d$, while the upper bound comes from $n(d_1)+n(d_2)\ge n(d_1+d_2)$ and some computer programs. I know that this is not always sufficient, e.g., for $d=14$ we need $n\ge 20$, but I conjecture that we need $n$ to be at most one bigger.

Probably I should also mention that this problem came up related to a search problem studied at our university search seminar and some of the above observations are joint works with others.

  • $\begingroup$ The following three explanations do not really line up with each other: "$f(xb)$ has one more $1$ than $f(x)$", "01 and 011 can be mapped to 100 and 101", "or even to 100 and 111" (the second and third ones suggest that you are allowed only to replace zeroes with ones, which is clearly more restrictive than the first, and the third clearly contradicts the first). So, what exactly did you want to say? $\endgroup$ – fedja May 25 '14 at 15:08
  • $\begingroup$ @fedja Thanks, I fixed that. I could not decide if I should first state the problem with requiring adjacencies and then state my more general problem, or the other way around, that's why I messed it up. $\endgroup$ – domotorp May 25 '14 at 15:58
  • $\begingroup$ Why not just left-pad x in C_d with 0's and length info? Does that not give you the desired embedding with n at most d+ log d ? $\endgroup$ – The Masked Avenger May 28 '14 at 18:27
  • 1
    $\begingroup$ Where does the 1.29 come from? Also, have you tried computing the first few values of $n$ (as a function of $d$) and plugging these into the OEIS? $\endgroup$ – Marco Golla Jan 22 '15 at 20:42
  • 2
    $\begingroup$ @Marco: Question updated. I tried OEIS, no luck, though I only know the first six values and conjecture the rest. $\endgroup$ – domotorp Jan 22 '15 at 21:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.