Representation of general and polyhedral subsemilattices and sublattices of product spaces

AbstractIt is shown that each element of the lattice of meet (resp., join) sublattices of a product S of n chains has a representation as the intersection of n subsets of S, the ith of which is decreasing (resp., increasing) for each fixed value of the ith coordinate for each i. This result is applied to show that an arbitrary element of the lattice of sublattices of S has a representation as the intersection of n2 subsets, the ijth of which is decreasing for each fixed value of the ith and increasing for each fixed value of the jth coordinate for each i, j. Irreducible representations are given in each case, providing an alternative proof of an instance of Hashimoto's (1952) representation of sublattices of a distributive lattice. Moreover, irreducible representations are given for the polyhedral members of the lattice of closed convex subsets of n-dimensional Euclidean space that are at once subsemilattices or sublattices. It is alsoshown that the polyhedral subsemilattices and sublattices can be represented as duals respectively of pre-Leontief substitution systems and generalized network-flow problems. Finally, the problems of checking whether a polyhedral set is a subsemilattice or sublattice are reduced to that of solving a system of linear inequalities, thereby showing that these recognition problems can be solved in polynomial time