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.