2017/05/15 by Hiroshi Hirai, Hirai, Hiroshi, So Nakashima +1
Computer Science · #Advanced Algebra and Logic #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1705.05781
openalex publication_date 2017/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A modular semilattice is a semilattice generalization of a modular lattice. We establish a Birkhoff-type representation theorem for modular semilattices, which says that every modular semilattice is isomorphic to the family of ideals in a certain poset with additional relations.This new poset structure, which we axiomatize in this paper, is called a PPIP (projective poset with inconsistent pairs). A PPIP is a common generalization of a PIP (poset with inconsistent pairs) and a projective ordered space. The former was introduced by Barthélemy and Constantin for establishing Birkhoff-type theorem for median semilattices, and the latter by Herrmann, Pickering, and Roddy for modular lattices. We show the Θ(n) representation complexityand a construction algorithm for PPIP-representations of (\wedge, \vee)-closed sets in the product Ln of modular semilattice L. This generalizes the results of Hirai and Oki for a special median semilattice Sk. We also investigate implicational bases for modular semilattices. Extending earlier results of Wild and Herrmann for modular lattices, we determine optimal implicational bases and develop a polynomial time recognition algorithm for modular semilattices. These results can be applied to retain the minimizer set of a submodular function on a modular semilattice.