Wednesday, June 04, 2008

Name of a kind of weight function on a lattice ?

Suppose we have a lattice with elements min, max, and the usual join and meet operations. I define a function w() that maps elements of the lattice to reals, such that
  • w(min) = 0
  • w(max) = 1
  • If x > y, then w(x) > w(y)
  • let z = join(x,y). Then w(x) + w(y) >= w(z)
Note that the last condition is slightly weaker than the usual submodularity condition
w(x) + w(y) >= w(z) + w(u) (where u = meet(x,y)).

My question is: is there a well known name for such a weight function ? I've been trying to search various sources, and the closest I came to this was the notion of a 'rank' function for a lattice, which doesn't quite capture this sort-of-metric-property.

4 comments:

  1. subadditive increasing?

    ReplyDelete
  2. it sounds like a measure function?

    ReplyDelete
  3. sub-additive (monotone)

    ReplyDelete
  4. I don't know of a name for such a function, but it sounds like it would be easiest to consider as a probability measure on the lattice, considered as a set of subsets of max.

    Then you can notice that not all lattices will allow you to satisfy a strict inequality x > y implies w(x) > w(y); but you can also classify which lattices force this inequality to be non-strict. Intuitively, I guess it's possible iff the lattice is countable.

    From this line of thinking, you can also analyze your degrees of freedom in choosing w. For example, you can assign an arbitrary nontrivial weight to an arbitrary non-min/max element to begin with. This is more of a guess, but you might even be able to uniquely classify the weight by assigning arbitrary nontrivial values to a strong antichain with join = max. By "strong antichain" I mean that no pairwise meet is min.

    ReplyDelete

Disqus for The Geomblog