  We show that any DNNF circuit that expresses the set of linear orders over a
set of $n$ candidates must be of size $2^{\Omega(n)}$. Moreover, we show that
there exist DNNF circuits of size $2^{O(n)}$ expressing linear orders over $n$
candidates.
