Expansions of a Chord Diagram and Alternating Permutations

• Published in: The Electronic journal of combinatorics 2016-01, Vol.23 (1)
• Main Author: Nakamigawa, Tomoki
• Format: Article
• Language: English
• ISSN: 1077-8926; 1077-8926
• DOI: 10.37236/5120

A chord diagram is a set of chords of a circle such that no pair of chords has a common endvertex. A chord diagram $E$ with $n$ chords is called an $n$-crossing if all chords of $E$ are mutually crossing. A chord diagram $E$ is called nonintersecting if $E$ contains no $2$-crossing. For a chord diagram $E$ having a $2$-crossing $S = \{ x_1 x_3, x_2 x_4 \}$, the expansion of $E$ with respect to $S$ is to replace $E$ with $E_1 = (E \setminus S) \cup \{ x_2 x_3, x_4 x_1 \}$ or $E_2 = (E \setminus S) \cup \{ x_1 x_2, x_3 x_4 \}$. It is shown that there is a one-to-one correspondence between the multiset of all nonintersecting chord diagrams generated from an $n$-crossing with a finite sequence of expansions and the set of alternating permutations of order $n+1$.