Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have some ordered tuples $a,b,c$, and I am interested in the following relation:

$$ a\succ b \Leftrightarrow \max_i \{a_i-b_i\} >\max_i\{b_i-a_i\} $$

That is, I'm interested in the maximum difference between elements of the vectors. (I hope the notation is clear: $a_i$ is the $i^{th}$ element of the tuple.

It's clear that the relation is irreflexive, but what I want to know is: is it transitive or acyclic? That is, can you have vectors such that $a\succ b \succ c \succ a$? If there are such cycles, is there some property you could demand of your vectors such that they would be ruled out?

share|improve this question
    
If I understand you correctly, the relation is not reflexive, unless you change the strict inequality defining the relation to a non-strict one. –  user22705 Mar 30 '12 at 12:12
    
Yes, I originally had that, but then you can obviously have cycles where $a=b=c$ but they're not what I'm interested in. So I went for the strict relation. I forgot to refactor the preamble to my actual question. Thanks for pointing that out! –  Seamus Mar 30 '12 at 12:20

1 Answer 1

up vote 3 down vote accepted

Sure, just let $a = (10,1,1)$, $b = (1,9,2)$, $c = (8,1,4)$.

share|improve this answer
    
a \succ b as 10-1 = 9 > 8 = 9-1, b \succ c as 9 - 1 = 8 > 7 = 8 - 1. c \succ a as 4 - 1 = 3 > 2 = 10 - 8. –  Wonder Mar 30 '12 at 12:44
    
+1 nice, did you just trial-and-error? –  draks ... Apr 3 '12 at 10:32
    
Well basically it's clear that the condition will be violated if the pairs considered while comparing different tuples are different. From that, it is easy to infer the indices that need to be compared. This example naturally follows as long as we see that by 10 here I basically mean 'some large number N', and '9' and '8' are basically just a decreasing sequence from N. –  Wonder Apr 3 '12 at 19:43
    
Hypothesis: if the tuples are all "monotonic" (i.e. increasing or decreasing) then the relation is acyclic. Does that sound plausible? –  Seamus Jul 26 '12 at 15:26
    
Not really, you can use essentially the same counterexample and tweak the tuples to be monotonic: (23, 5, 1), (14, 13, 2), (21, 5, 4) –  Wonder Aug 2 '12 at 11:01

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.