Graph Orientations and Linear Extensions

• 成果类型: Article
• 署名作者: Iriarte, Benjamin
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2016.0845
• 发表日期: 2017
• 页码: 1219-1229
• 关键词: polytopes; entropy; number

摘要

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.