Crossings and Nestings in Tangled Diagrams

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

Abstract


A tangled diagram on $[n]=\{1,\dots,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.


Full Text: PDF