Deciding Frattini is NP-complete
type: Item
instance of: scholarly article
title: Deciding Frattini is NP-complete
zbMATH Open document ID: 0819.06010
DOI: 10.1007/BF02115815
author: C. H. Ryter
author: Jürg Schmid
published in: Order
publication date: 1995-08-24T00:00:00Z
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.
Mathematics Subject Classification ID: 06D05
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 720844
zbMATH Keywords: NP-completeness
zbMATH Keywords: finitely representable posets
zbMATH Keywords: Frattini sublattice
zbMATH Keywords: finite posets
zbMATH Keywords: Birkhoff duals of finite distributive lattices
MaRDI profile type: Publication
cites work: The Frattini sublattice of a finite distributive lattice
cites work: The Frattini sublattice of a distributive lattice
cites work: Frattini sublattices in varieties of lattices
cites work: Frattini sublattices of distributive lattices
cites work: On the Frattini sublattice of a finite distributive lattice
cites work: Remarks on Priestley duality for distributive lattices
cites work: Q4692885
cites work: Q4198056
cites work: Q5814847
cites work: On the Frattini sublattice of a lattice
cites work: The rank of a distributive lattice
full work available at URL: https://doi.org/10.1007/bf02115815
OpenAlex ID: W2014049130
description: scientific article; zbMATH DE number 720844