Optimal embeddings of odd ladders into a hypercube (Q5957299)

An embedding of a graph \(G\) into (the graph of) a hypercube of dimension \(k\) is called optimal if the number of vertices of \(G\) is greater than \(2^{k-1}\). A ladder is a graph consisting of two paths of the same length \(n\) and of \(n+1\) paths, called rungs, such that the corresponding vertices of the two paths are connected by one of the rungs. Such a ladder is called odd if all its rungs are of odd size. Continuing their own work (see [Eur. J. Comb. 18, 249-266 (1997; Zbl 0883.05041)]) and that of others (see \textit{S. Bezrukov}, \textit{B. Monien}, \textit{W. Unger} and \textit{G. Wechsung} [Discrete Appl. Math. 83, 21-29 (1998; Zbl 0906.05019)]) the authors prove that every odd ladder with rungs of sizes greater than 6 has an optimal embedding into a hypercube. An example of an odd ladder with ten rungs of sizes 3 and 5 is given, found by a computer program, which does not have an optimal embedding into a hypercube. It remains open whether each odd ladder with rungs of sizes at least 5 has an optimal embedding into a hypercube. All proofs depend on sophisticated investigations of so-called dense sets in hypercubes.