Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 –  Dmitri Feb 21 '10 at 11:04
2  
In a lattice $x \vee y$ denotes the greatest lower bound of $\{x,y\}$ and $x \wedge y$ the least upper bound. –  Gerald Edgar Feb 21 '10 at 11:31
    
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) –  Dmitri Feb 21 '10 at 12:47
1  
By the way, I seem to have reversed $\wedge, \vee$ in my comment. –  Gerald Edgar Feb 21 '10 at 13:28
1  
@Dmitri: Look at the tag "lattice" ... it is interesting that there are posts on both types of lattice that use the label. –  Gerald Edgar Feb 21 '10 at 17:45
show 1 more comment

3 Answers 3

up vote 8 down vote accepted

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

share|improve this answer
2  
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. –  Suresh Venkat Feb 21 '10 at 17:37
    
Edited to add a second attempt. –  Gerald Edgar Feb 21 '10 at 18:53
    
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 ! –  Suresh Venkat Feb 21 '10 at 20:23
add comment

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.

share|improve this answer
    
For this I think "antimonotonic" should be: $x < y \Longrightarrow f(x) > f(y)$. –  Gerald Edgar Feb 22 '10 at 13:02
    
yes. I was being sloppy with the definitions –  Suresh Venkat Feb 22 '10 at 18:01
add comment

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.

share|improve this answer
    
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. –  Suresh Venkat Feb 22 '10 at 18:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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