Deciding Frattini is NP-complete

DOI10.1007/BF02115815MaRDI QIDQ1344247zbMATH OpenOpenAlexFDO

Authors C. H. Ryter, Jürg Schmid

Publication date 24 August 1995

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02115815

zbMATH Keywords

Birkhoff duals of finite distributive latticesfinite posetsfinitely representable posetsFrattini sublatticeNP-completeness

Mathematics Subject Classification ID

Partial orders, general (06A06) Structure and representation theory of distributive lattices (06D05) Analysis of algorithms and problem complexity (68Q25)

Review text

The Frattini sublattice is the intersection of all maximal proper sublattices of a given lattice. Every lattice is the Frattini sublattice of some lattice [\textit{K. Koh}, Algebra Univers. 1, 104-116 (1971; Zbl 0237.06006)], every distributive lattice is the Frattini sublattice of some distributive lattice [\textit{M. E. Adams}, ibid. 3, 216-228 (1973; Zbl 0288.06015)], and there exist finite distributive lattices not isomorphic to the Frattini sublattice for any finite distributive lattice. The finite posets arising as Birkhoff duals of finite distributive lattices are called finitely representable [\textit{M. Abad} and \textit{M. E. Adams}, ibid. 32, No. 3, 314-329 (1994; Zbl 0808.06014)]. The main result here states that it is NP-complete to decide whether a finite poset is finitely representable.

Recommendations

• The Frattini sublattice of a finite distributive lattice
• Maximal sublattices of finite distributive lattices
• The complexity of cover graph recognition for some varieties of finite lattices
• scientific article; zbMATH DE number 1080538
• On the Computational Complexity of Algebra on Lattices

Cites work

• Frattini sublattices in varieties of lattices
• Frattini sublattices of distributive lattices
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 194916 (Why is no real title available?)
• scientific article; zbMATH DE number 3075836 (Why is no real title available?)
• On the Frattini sublattice of a finite distributive lattice
• On the Frattini sublattice of a lattice
• Remarks on Priestley duality for distributive lattices
• The Frattini sublattice of a distributive lattice
• The Frattini sublattice of a finite distributive lattice
• The rank of a distributive lattice

Cited in

(3)

• Maximal sublattices of finite distributive lattices
• The Frattini sublattice of a finite distributive lattice
• COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA

This page was built for publication: Deciding Frattini is NP-complete

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