Geodesic
Weak embeddings of posets to the Boolean lattice
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2018_20_1_a5,
     author = {P\'alv\"olgyi, D\"om\"ot\"or},
     title = {Weak embeddings of posets to the {Boolean} lattice},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2018},
     doi = {10.23638/DMTCS-20-1-7},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-7/}
}
TY  - JOUR
AU  - Pálvölgyi, Dömötör
TI  - Weak embeddings of posets to the Boolean lattice
JO  - Discrete mathematics & theoretical computer science
PY  - 2018
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-7/
DO  - 10.23638/DMTCS-20-1-7
LA  - en
ID  - DMTCS_2018_20_1_a5
ER  - 
%0 Journal Article
%A Pálvölgyi, Dömötör
%T Weak embeddings of posets to the Boolean lattice
%J Discrete mathematics & theoretical computer science
%D 2018
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-7/
%R 10.23638/DMTCS-20-1-7
%G en
%F DMTCS_2018_20_1_a5
Pálvölgyi, Dömötör. Weak embeddings of posets to the Boolean lattice. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1. doi : 10.23638/DMTCS-20-1-7. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-7/

Cité par Sources :