Iriarte, Benjamin Graph orientations and linear extensions. (English) Zbl 1386.90127 Math. Oper. Res. 42, No. 4, 1219-1229 (2017). Summary: Given an underlying undirected simple graph, we consider the set of its acyclic orientations. 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 set polytope and (2) strong concentration results for our enumerative 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. MSC: 90C27 Combinatorial optimization 90C35 Programming involving graphs or networks 05C20 Directed graphs (digraphs), tournaments 05C21 Flows in graphs 05C80 Random graphs (graph-theoretic aspects) 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut Keywords:acyclic orientation; linear extension; poset; comparability graph; stable set polytope PDFBibTeX XMLCite \textit{B. Iriarte}, Math. Oper. Res. 42, No. 4, 1219--1229 (2017; Zbl 1386.90127) Full Text: DOI arXiv