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?
  • 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