MIT Combinatorics Seminar

Crossings and nestings of matchings and partitions

Richard Stanley  (MIT)

Friday, October 29, 2004    4:15 pm    Room 2-338


Let M be a complete matching (graph with n disjoint edges) of the set {1,2,...,2n}. A crosssing (respectively, nesting) of M is two edges (i,j) and (k,m) of M such that i<k<j<m (respectively, i<k<m<j). It is well-known that the number of complete matchings of the set {1,2,...,2n} with no crossings or with no nestings is the Catalan number Cn. We discuss how the theory of oscillating tableaux, which originally arose in the representation theory of the symplectic and orthogonal groups and the Brauer algebra, can be used to obtain further results on crossings and nestings of matchings. In particular, if fn(i,j) is the number of complete matchings of {1,2,...,2n} with at most i mutually crossing edges and with at most j mutually nested edges, then fn(i,j)=fn(j,i). Moreover, the Gessel-Zeilberger reflection principle allows the determination of the generating function Fi(x) = ∑n≥0 fn(i,∞) x2n/(2n)!. Similar results hold when matchings are replaced with set partitions, using a variation of oscillating tableaux called vacillating tableaux. This is joint work with William Y. C. Chen, Eva Y. P. Deng, Rosena R. X. Du, and Catherine H. Yan.