Monday, 2 February 2009

mg.metric geometry - Constructing a metric over a lattice

Consider a lattice $({cal L}, wedge, vee)$ with an antimonotonic function $f: {cal L} rightarrow {mathbb R}$ defined on it (i.e $x preceq y implies f(x) ge f(y)$).



$f$ is said to be submodular if for all $x,y in {cal L}$, $$f(x) + f(y) ge f(x wedge y) + f(x vee y)$$ and supermodular if the inequality is flipped (again for all $x,y$).



It's generally known (there's an easy proof), that a submodular $f$ induces a metric on ${cal L}$ via the defn $$ d_s(x,y) = 2f(x wedge y) - f(x) - f(y)$$. If $f$ is supermodular, then the construction $$d^s(x,y) = f(x) + f(y) - 2f(x vee y)$$ yields a metric.



Question I'm dealing with an $f$ that is nether sub- nor supermodular. I can define the "distance" $$ d(x,y) = min ( d^s(x,y), d_s(x,y))$$



Conjecture: $d(x,y)$ is a metric.



I have very little sound mathematical intuition for why this conjecture should be true, and bucketloads of empirical evidence (from a lattice I'm actually working with). This seems like the kind of thing that if true, would be reasonably well known to experts, and if false, might have a clear counterexample. So this is a plea for help.



Since it might make a difference, I should mention that the lattice I'm working with is nondistributive in general, but it has distributive sublattices where I'm still unable to prove the conjecture.

No comments:

Post a Comment