Generic rectangulations and pattern-avoiding permutations

Series
Combinatorics Seminar
Time
Friday, April 15, 2011 - 3:00pm for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Nathan Reading – North Carolina State University – http://www4.ncsu.edu/~nreadin/
Organizer
Christine Heitsch
A rectangulation is a tiling of a rectangle by rectangles. The rectangulation is called generic if no four of its rectangles share a corner. We will consider the problem of counting generic rectangulations (with n rectangles) up to combinatorial equivalence. This talk will present and explain an initial step in the enumeration: the fact that generic rectangulations are in bijection with permutations that avoid a certain set of patterns. I'll give background information on rectangulations and pattern avoidance. Then I'll make the connection between generic rectangulations and pattern avoiding permutations, which draws on earlier work with Shirley Law on "diagonal" rectangulations. I'll also comment on two theories that led to this result and its proof: the lattice theory of the weak order on permutations and the theory of combinatorial Hopf algebras.