Parallel sorting

We show that if n is sufficiently large then there is a graph G of order n with ⌊n 3 2logn⌋ edges such that the transitive closure of every acyclic orientation of G has at least n 2-n 3 2logn edges. A consequence of this is that with ⌊n 3 2logn⌋ parallel processors n objects may be sorted in two time intervals. This improves considerably some results of Häggkvist and Hell. We prove similar assertions about sorting with only d-step implications. © 1983