Expansions of a chord diagram and alternating permutations

Tomoki Nakamigawa¹

¹Shonan Institute of Technology

The electronic journal of combinatorics, Tome 23 (2016) no. 1

Résumé

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$.

Détail

DOI : 10.37236/5120

Classification : 05A19, 05A05
Mots-clés : chord diagram, alternating permutation, entringer number, Ptolemy's theorem