Embedding complete trees into the hypercube

Abstract We consider embeddings of the complete t -ary trees of depth k (denotation T k , t ) as subgraphs into the hypercube of minimum dimension n . This n , denoted by dim( T k , 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( T k ,3 )⩽2 k +1 up to lim k →∞ dim( T k ,3 )/ k ⩽5/3 and show lim t →∞ dim( T 3, 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( T k , t ) for arbitrary k and t .