Transitive Orientations of Graphs
Béla Bollobás, Graham Brightwell · SIAM Journal on Computing · 1988
Suppose that we have a set X of n objects in some unknown total order $ < $. For G a graph on X, we ask, for each edge $xy$, “Is $x < y$?” On processing the information thus gained we may be able to deduce more comparisons. The information we have is then in the form of a partial order $P(G; <)$. Let $t(G)$ denote the maximum, over all linear orders $ <$ on X, of the number of pairs not related in $P(G; <)$; and let $t(n,p)$ denote the minimum of $t(G)$ over all graphs G with n vertices and $\lfloor {{{pn^2 } / 2}} \rfloor $ edges. We find upper and lower bounds for $t(n,p)$ throughout the range of $p = p(n)$.