Complexity of cover-preserving embeddings of bipartite orders into Boolean lattices

DOI10.4467/20842589RM.14.006.2276zbMATH Open1355.06006OpenAlexW1912066678MaRDI QIDQ5499652FDOQ5499652

Authors: Grzegorz Herman 

Publication date: 30 July 2015

Full work available at URL: https://dblp.uni-trier.de/db/journals/rml/rml49.html#Herman14

Recommendations

• Cover-preserving embeddings of bipartite orders into Boolean lattices
• Weak embeddings of posets to the Boolean lattice
• Embedding ordered sets into distributive lattices
• Cover-preserving order embeddings into Boolean lattices
• The complexity of embedding orders into small products of chains

zbMATH Keywords

NP-completenessembeddabilityBoolean latticebipartite orderscover-preserving embeddings

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Combinatorics of partially ordered sets (06A07) Structure theory of lattices (06B05)

Cited In (3)

• Embedding ordered sets into distributive lattices
• Cover-preserving order embeddings into Boolean lattices
• Weak embeddings of posets to the Boolean lattice

This page was built for publication: Complexity of cover-preserving embeddings of bipartite orders into Boolean lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5499652)