User Tools

Site Tools


Richard Behr (Binghamton)

Acyclic Orientations of a Comparability Graph With the Most Linear Extensions

Abstract for the Combinatorics Seminar 2014 November 25

From a comparability graph G and an acyclic orientation of its edges we obtain a poset P. Which orientations of G will induce a poset with the maximum number of linear extensions? I will first provide an answer to this question using the order and chain polytopes of P and then look at the question from a different point of view using network flows.

This talk complements the recent one by Melissa Fuentes on another aspect of the topic and is based on the same paper, “Graph orientations and linear extensions” by Benjamin Iriarte (preprint, 2014). The previous talk is not prerequisite.

seminars/comb/abstract.201411beh.txt · Last modified: 2020/01/29 14:03 (external edit)