1
$\begingroup$

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

  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
  2. Is there an algorithm to find that/those minimum sets?
  • 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.2011-12-14
  • 0
    So n pairs is the minimum, but is there an algorithm to find those pairs?2011-12-14

2 Answers 2

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.

  • 0
    So $G$ must be connected and have exactly $n-1$ edges, and that is a sufficient condition for having the complete $<$ ?2011-12-14
  • 0
    @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.2011-12-14
  • 0
    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.2011-12-14
  • 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.2011-12-14
1

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.

  • 0
    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).2011-12-14