I was wondering under what circumstances, given a set of pairwise orderings $S=\{O_1, O_2, \cdots, O_k\}$, what conditions $S$ must satisfy (given $n$ total elements) before the ordering determined is unique. For example, given four elements total $E_1, E_2, E_3, E_4$, let $S$ be the set of conditions
- $E_4$ must precede $E_3$.
- $E_3$ must precede $E_2$.
- $E_2$ must precede $E_1$.
There is only one such ordering that is valid then, and it is the ordering $\{E_4, E_3, E_2, E_1\}$. My guess is that, a unique ordering can be deduced if and only if there are at least $n - 1$ conditions that "touch" all elements, and no subset of them contradict. Is this correct, and if so, what might be a way to formalize such a statement?
Thanks!
Your condition is not quite sufficient; using $\le$ to refer to precedence in the order, the list of $n-1$ conditions $1\le 2,1\le 3,\dots,1\le n$ is non-contradictory and touches all elements, but does not determine the order. The conditions only determine that $1$ is the first element in the ordering; there are still $(n-1)!$ orderings consistent with this fact.
A set of conditions of the form $x_i\le y_i$, where $x_i,y_i\in \{1,2,\dots,n\}$, will determine the ordering if and only if there exists a permutation $\pi$ of $\{1,2,\dots,n\}$ such that the conditions $\pi_k\le \pi_{k+1}$ are all given, for $k=1,2,\dots,n-1$. This is clearly sufficient to determine that $\pi$ is the true ordering. To see that it is necessary, suppose the true ordering is $\pi$, and for some $k$ the condition $\pi_k\le \pi_{k+1}$ is not given. Let $\hat \pi$ be the permutation attained from switching $\pi_k$ and $\pi_{k+1}$ in $\pi$. Then both $\pi$ and $\hat \pi$ are consistent with the given conditions, so the ordering is not determined.