KTH/SU Mathematics Colloquium

05-03-09

Richard Stanley, MIT

Crossings and nestings of matchings and set partitions

Abstract: Crossings and nestings are natural features of matchings (or fixed-point free involutions) and set partitions. We will show that they may be regarded as analogues of increasing and decreasing subsequences of permutations. Just as increasing and decreasing subsequences can be analyzed using standard Young tableaux, the RSK algorithm, and the Gessel-Zeilberger involution principle, so crossings and nesting can be analyzed using oscillating and vacillating tableaux, two analogues of the RSK-algorithm, and the Gessel-Zeilberger involution principle.