Embedding complete trees into the hypercube

We consider embeddings of the complete t-aly trees of depth k (denotation T-k,T- 1)) as subgraphs into the hypercube of minimum dimension n. This n, denoted by dim(T-k,T- t), is known if max {k, t} less than or equal to 2. First, we study the next open cases t = 3 and k = 3. We improve the known upper bound dim ( T-k,T- 3) less than or equal to 2k + 1 up to limk --> infinity dim(T-k,T- 3)/k less than or equal to 5/3 and show limt --> infinity dim(T-3,T- 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- t) for arbitrary k and t. (C) 2001 Elsevier Science B.V. All rights reserved.