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, d enoted by dim(T-k,T- t), is known if max {k, t} less than or equal to 2. Fi rst, we study the next open cases t = 3 and k = 3. We improve the known upp er bound dim ( T-k,T- 3) less than or equal to 2k + 1 up to limk --> infini ty 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 th e dimension of arbitrary trees of depth 2, as a function of their vertex de grees. 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 Sci ence B.V. All rights reserved.