Pálvölgyi, Dömötör (2018) Weak embeddings of posets to the boolean lattice. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 20 (1). ISSN 1462-7264
|
Text
1606.08226.pdf Download (144kB) | Preview |
Official URL: https://doi.org/10.23638/DMTCS-20-1-7
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 Patkós. 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 into the two middle levels of some hypercube. © 2018 by the author(s)
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > Q1 Science (General) / természettudomány általában |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 06 Mar 2023 11:05 |
| Last Modified: | 06 Mar 2023 11:05 |
| URI: | http://real.mtak.hu/id/eprint/161474 |
Actions (login required)
 |
Edit Item |
