User Tools

Site Tools


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.

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