The number of linear extensions of bipartite graphs (Q1114718)

A linear extension of a partially ordered set P is a total order L of elements of P such that \(x\leq y\) in P implies \(x\leq y\) in L. An acyclic directed graph G can be considered as a partial order on its vertex set; we have \(x\leq y\) in this order if and only if a directed path in G goes from x to y. A natural orientation of a bipartite graph with the bipartition classes \(V_ 1\), \(V_ 2\) is the orientation such that one of the sets \(V_ 1\), \(V_ 2\) is the set of initial vertices of all edges and the other is the set of all terminal ones. It is proved that any acyclic orientation of a bipartite graph G has a smaller number of linear extensions than a natural one. This was a conjecture of M. D. Atkinson.