6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Suresh, it will be very helpful if you explain in your question what your notations $L,\wedge,\vee$ mean. L stands for lattice, but what are $\wedge$ and $\vee$? I guess $x \wedge y$ does not mean wedge product of x and y ? – Dmitri $\endgroup$ Commented Feb 21, 2010 at 11:04
  • 2
    $\begingroup$ In a lattice $x \vee y$ denotes the greatest lower bound of $\{x,y\}$ and $x \wedge y$ the least upper bound. $\endgroup$ Commented Feb 21, 2010 at 11:31
  • $\begingroup$ Ok, I think I got, it, here by lattice we mean this: en.wikipedia.org/wiki/Partially_ordered_set , but not this: en.wikipedia.org/wiki/Lattice_(group) I was not awear of the first definition of Lattice, wiki is helpful here en.wikipedia.org/wiki/Lattice_(mathematics) $\endgroup$ Commented Feb 21, 2010 at 12:47
  • 1
    $\begingroup$ By the way, I seem to have reversed $\wedge, \vee$ in my comment. $\endgroup$ Commented Feb 21, 2010 at 13:28
  • 1
    $\begingroup$ @Dmitri: Look at the tag "lattice" ... it is interesting that there are posts on both types of lattice that use the label. $\endgroup$ Commented Feb 21, 2010 at 17:45

3 Answers 3

8
$\begingroup$

First failed attempt (this poset is not a lattice). Triangle inequality fails for the three .5 nodes in the middle:

...

Second attempt Our lattice consists of sets, with intersection and union. I show them by Venn diagrams here... The same three middle sets fail the triangle inequality for the same reasons as before. But now it is surely a lattice, right?

alt text

$\endgroup$
3
  • 2
    $\begingroup$ So I originally had a comment saying that this was a good example (and I also accepted the answer), but now I'm not so sure. In your example, let's label the three .5 elements A, B, C from left to right. Consider the "middle" .5 element B, and the .4 element "above" it in the drawing. These two elements have two meets in the lattice (the .9 and the .6). That violates the unique meet (and join) property of a lattice. I'm not certain there's an easy way to fix this. $\endgroup$ Commented Feb 21, 2010 at 17:37
  • $\begingroup$ Edited to add a second attempt. $\endgroup$ Commented Feb 21, 2010 at 18:53
  • $\begingroup$ I think this example works, but I'm going to let it stew in my head for a few hours before I accept it :). Thanks ! $\endgroup$ Commented Feb 21, 2010 at 20:23
1
$\begingroup$

Don't you need some strict inequality somewhere in your definitions? For example, a constant function meets your definitions of antimonotonic, submodular, and supermodular, but does not induce a metric (assuming your lattice has more than one element) since $d^s$ and $d_s$ would then always evaluate to zero.

$\endgroup$
2
  • $\begingroup$ For this I think "antimonotonic" should be: $x < y \Longrightarrow f(x) > f(y)$. $\endgroup$ Commented Feb 22, 2010 at 13:02
  • $\begingroup$ yes. I was being sloppy with the definitions $\endgroup$ Commented Feb 22, 2010 at 18:01
1
$\begingroup$

Probably to define a distance starting with a general antimonotonic $f$ we should do this: if $a\lt b$ then $d(a,b) = d(b,a) = f(a)-f(b)$, and for general $a,b$ let $d(a,b)$ be $$\inf \sum_{n=1}^n d(x_i,x_{i-1}),$$ where the infimum is over all sequences $a=x_0, x_1, \dots, x_n=b$ such that adjacent terms are comparable (call such sequences paths from $a$ to $b$). In your original proposal we used only two-step paths from $a$ to $b$, but to get the triangle inequality we need to allow longer paths as well. Presumably submodular implies that a certain two-step path is shortest, and supermodular that a different two-step path is shortest. Plus, this will apply to a poset that is not a lattice.

$\endgroup$
1
  • $\begingroup$ That's exactly right. That's how we did define a metric in fact. the original hope was that it could be computed easily using only two-step paths, and your example shows that this is not possible. $\endgroup$ Commented Feb 22, 2010 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.