×

Graph orientations and linear extensions. (English) Zbl 1386.90127

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
PDFBibTeX XMLCite
Full Text: DOI arXiv