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 |