Problem of the Week
Hilton Memorial Lecture
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.