Portal de Periódicos da CAPES

Crossings and Nestings in Tangled Diagrams

2008; Electronic Journal of Combinatorics; Volume: 15; Issue: 1 Linguagem: Inglês

10.37236/810

1097-1440

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

Topological and Geometric Data Analysis

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.