Deciding Frattini is NP-complete (Q1344247)

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.