Graph Orientations and Linear Extensions

Benjamin Iriarte ()
Additional contact information
Benjamin Iriarte: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Mathematics of Operations Research, 2017, vol. 42, issue 4, 1219-1229

Abstract: 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.

Keywords: acyclic orientation; linear extension; poset; comparability graph; stable set polytope (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0845 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:4:p:1219-1229

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().