Graph Orientations and Linear Extensions

DOI10.1287/MOOR.2016.0845MaRDI QIDQ4595964zbMATH OpenOpenAlexFDO

Authors Benjamin Iriarte

Publication date 7 December 2017

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.4880

zbMATH Keywords

acyclic orientationcomparability graphlinear extensionposetstable set polytope

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

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

Recommendations

• Graph orientations and linear extensions
• Orientations of graphs
• scientific article; zbMATH DE number 3957181
• On the orientation of graphs and hypergraphs
• scientific article; zbMATH DE number 729744
• scientific article; zbMATH DE number 17787
• An orientation theorem for graphs
• On oriented graphs with certain extension properties.
• Maximal orientations of graphs
• scientific article; zbMATH DE number 47434

Cited in

(3)

• The number of linear extensions of bipartite graphs
• scientific article; zbMATH DE number 1323403 (Why is no real title available?)
• Graph orientations and linear extensions

This page was built for publication: Graph Orientations and Linear Extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4595964)