Minimum size of a subset to know a complete total order

Question

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?

Answer 1

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.

Answer 2

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.