  Given an underlying undirected simple graph, we consider the set of all
acyclic orientations of its edges. Each of these orientations induces a partial
order on the vertices of our graph and, therefore, we can count the number of
linear extensions of these posets. We want to know which choice of orientation
maximizes the number of linear extensions of the corresponding poset, and this
problem will be solved essentially for comparability graphs and odd cycles,
presenting several proofs. The corresponding enumeration problem for arbitrary
simple graphs will be studied, including the case of random graphs; this will
culminate in 1) new bounds for the volume of the stable polytope and 2) strong
concentration results for our main statistic and for the graph entropy, which
hold true $a.s.$ for random graphs. We will then argue that our problem springs
up naturally in the theory of graphical arrangements and graphical zonotopes.
