Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

I think I can prove some upper and lower bounds (like $n\approx 1.29d$) but I wonder if this problem has been studied before. 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). Anyone every heard of this problem?

share|improve this question
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? –  fedja May 25 at 15:08
@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. –  domotorp May 25 at 15:58
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 ? –  The Masked Avenger May 28 at 18:27
@TheMaskedAvenger: I have no clue what you mean but certainly not as I have a lower bound of 1.29d for n. –  domotorp May 28 at 20:33
Then I am misunderstanding something. For clarity, I recommend saying "n at least 1.29d", as the present phrase does not indicate which type of bound and now I am unsure if that value is feasible or only necessary. –  The Masked Avenger May 28 at 20:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.