On the combinatorial structure of Rauzy graphs

M. B. Dubashinsky

Informatics and Automation, Mathematical control theory and differential equations, Tome 277 (2012), pp. 57-73

Résumé

Let $S_m^0$ be the set of all irreducible permutations of the numbers $\{1,\dots,m\}$ ($m\ge3$). We define Rauzy induction mappings $a$ and $b$ acting on the set $S_m^0$. For a permutation $\pi\in S_m^0$, denote by $R(\pi)$ the orbit of the permutation $\pi$ under the mappings $a$ and $b$. This orbit can be endowed with the structure of an oriented graph according to the action of the mappings $a$ and $b$ on this set: the edges of this graph belong to one of the two types, $a$ or $b$. We say that the graph $R(\pi)$ is a tree composed of cycles if any simple cycle in this graph consists of edges of the same type. An equivalent formulation of this condition is as follows: a dual graph $R^*(\pi)$ of $R(\pi)$ is a tree. The main result of the paper is as follows: if the graph $R(\pi)$ of a permutation $\pi\in S_m^0$ is a tree composed of cycles, then the set $R(\pi)$ contains a permutation $\pi_0\colon i\mapsto m+1-i$, $i=1,\dots,m$. The converse result is also proved: the graph $R(\pi_0)$ is a tree composed of cycles; in this case, the structure of the graph is explicitly described.