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, $c, $d, $ e. From that, we can conclude that $c, so we know all the values of $<$ .
  2. Is there an algorithm to find that/those minimum sets?
  • 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.

  • 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