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