On the dimension of trees (Q5916234)

This short article considers the problem of isometrically embedding a tree into the graph \(Z_m\), which has as vertices the lattice points of the \(m\)-dimensional space. Two vertices \(a\), \(b\) are adjacent if and only if \(| a_i-b_i| \leq 1\), where \(a_i\), \(b_i\) are the vertex coordinates. The authors show that the embedding is possible if \(\lceil\log_2 t\rceil\leq m \leq \lceil1.45\log_2 t\rceil\), thus improving the lower bound and the previously best known upper bound of about \(1.71\log_2 t\) (\(t\) is the number of leaves of the tree).