Generating uniform linear extensions using few random bits

Mark Huber

A \emph{linear extension} of a partial order \(\preceq\) over items \(A = \{ 1, 2, \ldots, n \}\) is a permutation \(σ\) such that for all \(i < j\) in \(A\), it holds that \(\neg…