Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: The Weak Bruhat Order, Persistent Graphs and Staircase Polygon Visibility
Speaker: James Abello, DIMACS
Date: Thursday, April 22, 2010 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
We introduce a special class of graphs called Persistent. They partition maximal chains on the Weak Bruhat Order of the Symmetric Group. It has been known for some time that visibility graphs of staircase polygons are contained in the class of persistent graphs ( AEK, Discrete and Computational Geometry, 14:331-358, 1995 ). A two decades conumdrum has been to prove that these two classes are identical. We will highlight the main elements of such a proof. As a byproduct we obtain an efficient algorithm that constructs for a given persistent graph G a staircase polygon P whose visibility graph is isomorphic to G.