A note on supermodular sublattices in finite relatively complemented lattices
type: Item
instance of: scholarly article
title: A note on supermodular sublattices in finite relatively complemented lattices
zbMATH Open document ID: 1170.06001
author: Benoît Larose
author: Andrei Krokhin
published in: Algebra Universalis
publication date: 2009-01-29T00:00:00Z
review text: Let \(L\) be a lattice and let \(\mathbb{R}\) denote the set of real numbers. A function \(f: L\rightarrow \mathbb{R}\) is called supermodular if it satisfies \(f(x)+f(y)\leq f(x\wedge y)+f(x\vee y)\) for all \(x, y\in L.\) Note that supermodular functions play an important role in some applications, such as in mathematical economics, operations research or computer science. In the last domain, supermodular functions occur in the study of the complexity of certain optimisation problems called maximum constraint satisfaction problems. We need one more concept: Let \(K\) be a sublattice of \(L.\) \(K\) is said to be supermodular (in \(L\)) if, for any \(x\in K\) and \(y\in L\), at least one of the elements \(x\wedge y, x\vee y\) belongs to \(K.\) It is easy to verify that an ideal or a filter or a union of an ideal and a filter is a supermodular sublattice of \(L.\) The following result is also easy to derive: Let \(f\) be a 0-1 valued function on \(L\). Then \(f\) is supermodular on \(L\) iff \(\{x\in L: f(x)=1\}\) is a supermodular sublattice of \(L\). The main result describes the supermodular sublattices of a finite lattice \(L,\) where \(L\) is a direct product of non-trivial relatively complemented lattices.
Mathematics Subject Classification ID: 06B05
Mathematics Subject Classification ID: 06B10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5500527
zbMATH Keywords: lattices
zbMATH Keywords: supermodular functions
zbMATH Keywords: maximum constraint satisfaction
reviewed by: Tibor Katriňák
MaRDI profile type: Publication
full work available at URL: s00012-008-2123-8
OpenAlex ID: W2041594453
DOI: 10.1007/S00012-008-2123-8
description: scientific article; zbMATH DE number 5500527