Embedding complete trees into the hypercube Original Research Article

We consider embeddings of the complete t-ary trees of depth k (denotation Tk,t) as subgraphs into the hypercube of minimum dimension n. This n, denoted by dim(Tk,t), is known if max{k,t}⩽2. First, we study the next open cases t=3 and k=3. We improve the known upper bound dim(Tk,3)⩽2k+1 up to limk→∞dim(Tk,3)/k⩽5/3 and show limt→∞dim(T3,t)/t=227/120. As a co-result, we present an exact formula for the dimension of arbitrary trees of depth 2, as a function of their vertex degrees. These results and new techniques provide an improvement of the known upper bound for dim(Tk,t) for arbitrary k and t.