Simplicial elimination schemes,extremal lattices and maximal antichain lattices |
| |
Authors: | Michel Morvan Lhouari Nourine |
| |
Institution: | (1) LITP/IBP Université Denis Diderot Paris 7 Case 7014, 2, place Jussieu, 75251 Paris Cedex 05, France;(2) LIRMM (CNRS and Université Montpellier II), 191, rue Ada, 34092 Montpellier, France |
| |
Abstract: | Fix a partial order P=(X, <). We first show that bipartite orders are sufficient to study structural properties of the lattice of maximal antichains. We show that all orders having the same lattice of maximal antichains can be reduced to one representative order (called the poset of irreducibles by Markowsky 14]). We then define the strong simplicial elimination scheme to characterize orders which have distributive lattice of maximal antichains. The notion of simplicial elimination corresponds to the decomposition process described in 14] for extremal lattices. This notion leads to simple greedy algorithms for distributivity checking, lattice recognition and jump number computation. In the last section, we give several algorithms for lattices and orders. |
| |
Keywords: | 06AXX 06BXX 06DXX |
本文献已被 SpringerLink 等数据库收录! |
|