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.

Lets say we have a set $A$. Suppose that $A$ is ordered by $<$, $A$ is completely ordered.

$<$ can be defined as $<:=\{(a,b) \in A\times A : a<b \}$

  1. Given that $<$ is transitive, it is not necesary to know all the values of $<$, so what is the minimum amount of pairs in $<$ needed to know all the values of $<$. For example: Let $A = \{a,b,c,d,e\}$. Suppose we know $a<b$, $c<d$, $d<e$, $ e<a$. From that, we can conclude that $c<d<e<a<b$, so we know all the values of $<$ .
  2. Is there an algorithm to find that/those minimum sets?
share|improve this question
1  
If you know $a_1 < a_2, a_2 < a_3, \ldots, a_{n-1} < a_n$, then you can recover $\lt$ uniquely. So $n-1$ values suffice. It's not hard to show that this is also the minimum. –  Srivatsan Dec 14 '11 at 6:30
    
So n pairs is the minimum, but is there an algorithm to find those pairs? –  Woojah Dec 14 '11 at 7:07

2 Answers 2

We need at least $n-1$ entries of $\lt$ to uniquely reconstruct the total order. Construct an undirected graph $G$ with vertex set $A$ by adding an edge $xy$ if and only if we know the relative ordering between $x$ and $y$. It is easy to see if the total order can be uniquely reconstructed from the entries, then $G$ must be connected; hence $G$ should have at least $n-1$ edges.

In fact, $n-1$ entries suffice as well. For example, if we know that $a_1 < a_2 < \cdots < a_{n-1} < a_n$, then the total order is completely specified.

share|improve this answer
    
So $G$ must be connected and have exactly $n-1$ edges, and that is a sufficient condition for having the complete $<$ ? –  Woojah Dec 14 '11 at 7:09
    
@Woojah No, the converse is not true. E.g., if $A = \{ a, b, c \}$, then knowing that $a < c$ and $b < c$ does not recover $\lt$ uniquely. I think that if the graph has exactly $n-1$ edges, then it must be a path. –  Srivatsan Dec 14 '11 at 7:13
    
Okey, let me change the question a bit: what are the minimum amount of questions needed to know the complete $<$ relation. More precicely if I asked is $a < b$ for some $a,b\in A$ how many pairs do I need to ask in order to know the complete $<$ relation. Note that it is not $n-1$ because the answer will not always be favorable. btw, thanks for the help from before. –  Woojah Dec 14 '11 at 15:50
1  
@Woojah: with this comment you have the problem of sorting $n$ elements of a list, which can be done in about $n \log_2 n$ comparisons. This is a problem that has been worked extensively in computer science. –  Ross Millikan Dec 14 '11 at 22:19

The question is equivalent to "how many pairwise comparisons are needed to sort a list of $n$ elements?" Clearly the answer must be at least $\log_{2}(n!)=n\log_{2}n + O(n)$ in the worst case, since there are $n!$ possibilities to distinguish and each comparison has only $2$ possible outcomes... this gives a lower bound. On the other hand, there are examples of sorting algorithms that operate using $O(n\log n)$ comparisons (e.g., merge sort), giving an upper bound. Therefore the answer is $\Theta(n\log_2{n})$.

I am assuming that you are allowed to choose which elements to compare based on the results of previous comparisons. If you are not, then the answer is simply $\frac{1}{2}n(n-1)$: all pairwise comparisons need to be made. For every pair $(a,b)$, there are orderings where $a$ and $b$ are adjacent and cannot be placed relative to each other without being directly compared.

share|improve this answer
    
Srivistan's comment and answer show how this can be done with $n-1$ comparisons (if you get the right ones, which is the spirit of the question). –  Ross Millikan Dec 14 '11 at 22:16

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.