Richard Behr (Binghamton)

Graph Orientations and Linear Extensions

Abstract for the Combinatorics Seminar
2015 April 21

Consider the set of all acyclic orientations of the edges of a simple graph G. Each orientation induces a partial order on the vertices of G. One can count the number of linear extensions of such posets. We want to know which orientations give posets that have the maximum number of linear extensions. The question is easily answered for comparability graphs; this solution is related to a certain convex polytope (Stanley's order polytope), network flows, and more.


To the Combinatorics Seminar Web page.