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.
