Weak embeddings of posets to the Boolean latticeArticle
Authors: Dömötör Pálvölgyi
0000-0003-2970-0943
Dömötör Pálvölgyi
The goal of this paper is to prove that several variants of deciding whether
a poset can be (weakly) embedded into a small Boolean lattice, or to a few
consecutive levels of a Boolean lattice, are NP-complete, answering a question
of Griggs and of Patkos. As an equivalent reformulation of one of these
problems, we also derive that it is NP-complete to decide whether a given graph
can be embedded to the two middle levels of some hypercube.