Dense sets and embedding binary trees into hypercubes

AbstractThe purpose of this paper is to describe a method for embedding binary trees into hypercubes based on an iterative embedding into their subgraphs induced by dense sets. As a particular application, we present a class of binary trees, defined in terms of size of their subtrees, whose members allow a dilation two embedding into their optimal hypercubes. This provides a partial evidence in favor of a long-standing conjecture of Bhatt and Ipsen which claims that such an embedding exists for an arbitrary binary tree