COVER-PRESERVING ORDER EMBEDDINGS INTO BOOLEAN LATTICES

It is not known which finite graphs occur as induced subgraphs of a hypercube. This is relevant in the theory of parallel computing. The ordered version of the problem is: Which finite posets P occur as cover-preserving subposets of a Boolean lattice? Our main Theorem gives (for 0, 1-posets) a necessary and sufficient condition, which involves the chromatic number of a graph associated to P. It is applied respectively to upper balanced, meet extremal, meet semidistributive, and semidistributive lattices P. More specifically, we consider isometric embeddings of posets into Boolean lattices. In particular, answering a question of Ivan Rival to the positive, a nontrivial invariant for the covering graph of a poset is found.