Embedding ordered sets into distributive lattices

DOI10.1007/S11083-015-9376-6MaRDI QIDQ2520717zbMATH OpenOpenAlexFDO

Authors C. J. van Alten

Publication date 16 December 2016

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11083-015-9376-6

zbMATH Keywords

distributive latticeNP-completenessordered set

Mathematics Subject Classification ID

Partial orders, general (06A06) Structure and representation theory of distributive lattices (06D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Review text

In this paper, the author investigates the decision problem: DistPO: Given a finite ordered set, is it embeddable into a distributive lattice with preservation of existing meets and joins? The main result of the paper is that DistPO is NP-complete. The NP-hardness is achieved by a polynomial reduction to the 3SAT decision problem to DistPO and membership in NP is proved by presenting a suitable NP-algorithm. The author also shows that the results above extend to the bounded case, i.e., to the decision problem: BoundedDistPO: Given a finite bounded ordered set, is it embeddable into a bounded distributive lattice with preservation of existing meets and joins? The requirement that all existing finite meets and joins are preserved could be weakened so that only joins of sets up to size \(k\) and meets of sets up to size \(p\) are preserved where \(k, l\geq 2\). The author shows that NP-completeness holds in the case \(k\geq 3\) and \(l\geq 2\). The case \(k=l=2\) is left open.

Recommendations

• Complexity of cover-preserving embeddings of bipartite orders into Boolean lattices
• Weak embeddings of posets to the Boolean lattice
• Embeddings of finite distributive lattices into products of chains
• On the embedding of distributive lattices into recursive polynomial degrees
• The complexity of the fixed point property

Cites work

• Canonical extensions of posets.
• scientific article; zbMATH DE number 6006014 (Why is no real title available?)
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 1554928 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• Lattices and bases of Coxeter groups
• Order dimension, strong Bruhat order and lattice properties for posets
• Partially Ordered Sets
• The complexity of embedding orders into small products of chains
• The Complexity of the Partial Order Dimension Problem

Cited in

(14)

• \(\kappa\)-embeddings of ordered sets
• Embeddings of finite distributive lattices into products of chains
• No finite axiomatizations for posets embeddable into distributive lattices
• Packing problems, dimensions and the tensor product of complete lattices
• Large Sets of Lattices without Order Embeddings
• scientific article; zbMATH DE number 3887755 (Why is no real title available?)
• Weak embeddings of posets to the Boolean lattice
• Distributive and completely distributive lattice extensions of ordered sets
• Closure operators, frames and neatest representations
• The logic of information in state spaces
• Recursive axiomatisations from separation properties
• Complexity of cover-preserving embeddings of bipartite orders into Boolean lattices
• Atomic Boolean lattice completions of ordered sets
• Ordering the order of a distributive lattice by itself

This page was built for publication: Embedding ordered sets into distributive lattices

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