DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

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

Abstract:

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.