Crossings and Nestings in Tangled Diagrams

William Y.C. Chen, Jing Qin, and Christian M. Reidys

  Abstract:  A tangled diagram on [n] = {1,..., n} is a labeled graph for which each vertex has degree at most two. The vertices are arranged in increasing order on a horizontal line and the arcs are drawn in the upper halfplane with a particular notion of crossings and nestings. Generalizing the construction of Chen et al., we give a bijection between generalized vacillating tableaux with less than k rows and k-noncrossing tangled diagrams. We show that the numbers of k-noncrossing and k-nonnesting tangled diagrams are equal and we enumerate k-noncrossing tangled diagrams. Finally, we show that braids, a special class of tangled diagrams, facilitate a bijection between 2-regular k-noncrossing partitions and k-noncrossing enhanced partitions.

  AMS Classification:  05A18

  Keywords:  tangled-diagram, partition, matching, crossing, nesting, vacillating tableau.

  Download:   PDF