Generic rectangulations and pattern-avoiding permutations

Combinatorics Seminar
Friday, April 15, 2011 - 15:00
1 hour (actually 50 minutes)
Skiles 006
North Carolina State University
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.