SUPERMODULAR FUNCTIONS ON LATTICES
David Promislow (York University)
Let L be a finite lattice, that is,
L is a finite set equipped with a
partial order, such that every pair of elements
x,y has a least
upper bound x v y and a greatest lower bound xy .
A real valued
function f on L is said to be
supermodular if for all x,y in
L
f(x v y) + f(xy) >= f(x) + f(y)
If equality holds for all x and y, f
is said to be modular
The problem we consider is that of determining the extreme rays
of the
quotient S/M where S is the cone
of supermodular functions, and M
is the vector space of modular functions. ( A ray
R in a cone K is said
to be extreme if a =b+c where a is in R and
b,c are in K
implies that b,c are in R.)
This was motivated by problems in probability theory dealing with
stochastic orderings.( The particular application is to determine
dominance for the supermodular ordering on multivariate distributions)
We are able to solve this problem completely for the simplest
type of
lattices, namely those which are the disjoint
union of chains.
For the particular application, we are interested in the lattice
Z_N ^k
consisting of all k -tuples with entries from the set
{0,1, ... N-1},
equipped with the usual pointwise order. We are able
to get complete
answers for the cases : k = 2; N=2 , k= 3 or 4;
N=3, k = 3.
We present some conjectures for the general case .
Applied Algebra seminar home