Melissa Fuentes (Binghamton)

Acyclic Orientations of Bipartite Graphs and Their Linear Extensions

Abstract for the Combinatorics Seminar
2014 November 11

Given an undirected bipartite graph G=(V,E), I consider its acyclic edge orientations (that is, the edges of no cycle are consistently oriented). Each acyclic orientation induces a partial order on V. I will examine which acyclic orientations maximize the number of linear extensions of that partial order. I will prove that two particular orientations of G uniquely maximize the number of extensions.


To the Combinatorics Seminar Web page.