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

Crossings and nestings in tangled diagrams

Electron. J. Comb. 15(1), Research Paper R86, 14 p. (2008)

Summary

Summary: 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.

Mathematics Subject Classification

05A18

Downloads