Embedding complete trees into the hypercube (Q5936455)

For given tree \(T\), the dimension of \(T\) (denoted by \(\text{dim}(T)\)) is the minimum \(n\) such that \(T\) is a subgraph of the \(n\)-dimensional hypercube. In the paper, the dimension of complete \(t\)-ary trees \(T^{k,t}\) of depth \(k\) is considered. It is known that \(\frac{kt}{e} \leq \dim(T^{k,t}) \leq \frac{(k+1)t}{2}+k-1\) [see \textit{F. Ollé}, M. Sci. Thesis, Math. Inst. Prague (1972)], \(\dim(T^{k,2})=k+2\), \(k \geq 2\) and \(\dim(T^{2,t})=\lceil \frac{3t+1}{2}\rceil\), \(t \geq 1\) [see \textit{I. Havel} and \textit{P. Liebl}, Čas. Pěst. Mat. 97, 201-205 (1972; Zbl 0229.05109) and Čas. Pěst. Mat. 98, 307-314 (1973; Zbl 0274.05101)]. For the next open cases \(k=3\) and \(t=3\), it is known that \(\dim(T^{3,t}) \leq 2t+2\), \(\dim(T^{k,3}) \leq 2k +1\) (H.-D. O. F. Gronau and J.-M. Laborde (1994)). The author improves the leading coefficients 2 in these upper bounds, showing that \[ \lim_{k \to \infty}\frac{\dim(T^{k,3})}{k} \leq \frac{5}{3}\quad\text{and}\quad\lim_{t \to \infty}\frac {\dim(T^{3,t})}{t} = \frac{227}{120}. \] Also, the general upper bound is improved asymptotically by showing that \[ \lim_{k,t \to \infty} \frac{\dim(T^{k,t})}{kt} \leq \frac{307}{640}. \] As a co-result, an exact formula for the dimension of arbitrary trees of depth 2 as a function of their vertex degrees is presented.