Problem of the Week
Hilton Memorial Lecture
Consider the set of all acyclic orientations of the edges of a simple graph G. Each orientation induces a partial order on the vertices of G. One can count the number of linear extensions of such posets. We want to know which orientations give posets that have the maximum number of linear extensions. The question is easily answered for comparability graphs; this solution is related to a certain convex polytope (Stanley's order polytope), network flows, and more.