Weak embeddings of posets to the Boolean lattice
From MaRDI portal
Publication:4560229
zbMATH Open1401.05292arXiv1606.08226MaRDI QIDQ4560229
Publication date: 10 December 2018
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1606.08226
Combinatorics of partially ordered sets (06A07) Extremal set theory (05D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
This page was built for publication: Weak embeddings of posets to the Boolean lattice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4560229)
