• PDF
• Cite
• Share
Article Contents  Article Contents

# A combinatorial approach to Rauzy-type dynamics II: The labelling method and a second proof of the KZB classification theorem

• Rauzy-type dynamics are group actions on a collection of combinatorial objects. The first and best known example (the Rauzy dynamics) concerns an action on permutations, associated to interval exchange transformations (IET) for the Poincaré map on compact orientable translation surfaces. The equivalence classes on the objects induced by the group action have been classified by Kontsevich and Zorich, and by Boissy through methods involving both combinatorics algebraic geometry, topology and dynamical systems. Our precedent paper  as well as the one of Fickenscher  proposed an ad hoc combinatorial proof of this classification.

However, unlike those two previous combinatorial proofs, we develop in this paper a general method, called the labelling method, which allows one to classify Rauzy-type dynamics in a much more systematic way. We apply the method to the Rauzy dynamics and obtain a third combinatorial proof of the classification. The method is versatile and will be used to classify three other Rauzy-type dynamics in follow-up works.

Another feature of this paper is to introduce an algorithmic method to work with the sign invariant of the Rauzy dynamics. With this method, we can prove most of the identities appearing in the literature so far (, , , ...) in an automatic way.

Mathematics Subject Classification: A5A05, 30F30, 32G15, 37A05, 37B05.

 Citation: • • Figure 1.  Let $x\in X_n$ be a combinatorial structure on $n$ vertices. $A_x$ choose a permutation $\sigma$ depending on $x$ and permutes the vertices of $x$ according to it. We represent this symmetric-group action as a diagrammatic action from below

Figure 2.  $S'$ is a boosted sequence of $S$ for $(x, c)$, because $\text{red} \circ S'$ gives the same result as $S \circ \text{red}$. Note that $S'$ may be not unique: in the diagram we show a second boosted sequence of $S$ for $(x, c)$, namely $S"$. It is not necessarily the case that $(x', c') : = S'(x, c)$ coincides with $(x", c") : = S"(x, c)$, but merely that their reductions coincide (they must be both $y'$)

Figure 3.  A representation of a combinatorial structure $x\in X_n$ with a labelling $\Pi_b.$ The intervals are represented by the bottoms arcs

Figure 4.  Outline of the proof of connectivity between $x_1$ and $x_2$, using the labelling method. The sequence $S$ sends $y_1$ to $y_2$, however the intervals containing the gray vertices of $x'_1$ may not be at their correct place, in order to match with those of $x'_2$. The sequence $S_*$ corrects for this. Thus the boosted sequence $S'_* S'$ sends $x'_1$ to $x'_2$, and $x_1$ and $x_2$ are connected

Figure 5.  Diagram representations of matchings and permutations, and matrix representation of permutations

Figure 6.  Our two main examples of dynamics, in diagram representation. Top: the $\mathcal{M}_n$ case. top: the $\mathcal{S}_n$ case

Figure 7.  The Rauzy dynamics concerning permutations, in matrix representation

Figure 8.  Left: A reducible permutation in matrix representation; the $\mathcal{S}$ dynamic acts on the first block with $L$ and $R$. Right: A reducible permutation in diagram representation; the $\mathcal{S}$ dynamics acts on the gray part with $L$ and $R$, while leaving the blue part unchanged

Figure 9.  Left: an irreducible permutation, $\sigma = [\, 451263\, ]$. Right: the construction of the cycle structure. Different cycles are in different colours. The length of a cycle or path, defined as the number of top (or bottom) arcs, is thus 2 for red and violet, and 1 for blue. The green arrows are the endpoints of the rank path, which is in blue. As a result, in this example $\lambda (\sigma ) = (2, 2)$ (for the cycles of color red and violet), $r(\sigma ) = 1$ (corresponding to the rank path of color blue), and $\ell(\sigma ) = 2$

Figure 10.  Left: an example of permutation, $\sigma = [\, 251478396\, ]$. Right: an example of subset $I = \{1, 2, 6, 8, 9\}$ (labels are for the bottom endpoints, edges in $I$ are in blue). There are two crossings, out of the maximal number $\binom{|I|}{2} = 10$, thus $\chi_I = 8$ in this case, and this set contributes $(-1)^{|I|+\chi_I} = (-1)^{5+8} = -1$ to $A(\sigma )$

Figure 11.  Two consistent labellings $(\Pi_b, \Pi_t)$ and $(\Pi'_b, \Pi'_t)$ of a permutation $\sigma$ with cycle invariant $(\{2, 2, 2\}, 2)$. Following definition 26 we have $(\Pi'_b, \Pi'_t) = \mathrm{Sh}^1_{2, 1}((\Pi_b, \Pi_t))$

Figure 12.  The action on the dynamics (with an $L$ operator) on a consistent labelling

Figure 13.  The proof that $\Pi'_b$ verifies property 2 and $(\Pi'_b, \Pi'_t)$ verifies property 3 for the case $\alpha\leq \sigma (1)$

Figure 14.  The proof that $\Pi'_b$ verifies property 2 and $(\Pi'_b, \Pi'_t)$ verifies property 3 for the case $\alpha = \sigma (1)+1$

Figure 15.  The gray edges of $\sigma$ are transported along the labels of the arcs when applying the boosted dynamics. For instance, $e\in(b, t)$ in $\tau, \Pi$

Figure 16.  Illustration that the edges, inserted within the labels of a reduced permutation, follow those labels when applying the boosted dynamic

Figure 17.  Left: a schematic representation of a permutation of type $H(r_1, r_2)$. Right: a representation of a permutation of type $X(r, i)$. These configurations have rank $r_1+r_2-1$ and $r$, respectively

Figure 18.  The insertion of one edge within the arcs $\alpha$ and $\beta$

Figure 19.  The first line represents the case: Top arc : any cycle. Bottom arc: any cycle. The second line represents the case: Top arc : rank path. Bottom arc: principal cycle

Figure 20.  The first column represents the permutation $\sigma$ and its the cycle invariant. The second column represents the permutation $\sigma '$ obtained from the insertion of a double-edge within the arcs $\alpha$ and $\beta$ of $\sigma$ and the third column displays and demonstrates the new invariant of $\sigma '$

Figure 21.  An example of a shift-irreducible family $S = (\sigma ^i)_{0\leq i \leq n-2}$ with its two unavoidably reducible permutations $d(\sigma ^{n-\sigma (2)})$ and $d(\sigma ^{n-\sigma (n)+1}).$ For a proof of the shift-irreducibility, the characterisation proposition 44 is helpful

Figure 22.  The two permutations $\sigma ^{n-\sigma (2)}$ and $\sigma ^{n-\sigma (n)+1}$ are of type $H(1, r)$ and $H(r, 1)$ respectively

Figure 23.  The permutation $\sigma _{1, 4, \{(0.1, 0.1), (0.2, 3.1), (0.3, 1.1), (1.1, 4.1), (1.2, 2.1)\}}$. We cannot show the full matrix $Q$ for such a big example, but we can give one row, for the edge which has the label $e$ in the drawing. The row $Q_e$ reads $(Q_e)_{11, 12, \ldots, 15, 21, \ldots, 25} = (1, 1, 0, 0, 0, \, 0, 0, 1, 1, 1)$

Figure 24.  From left to right: the permutations $\sigma$, $\sigma |_{1, \alpha, \beta}$ and $\sigma |_{1, \alpha, \beta'}$. The proposition 53 says that $\sigma |_{1, \alpha, \beta}$ and $\sigma |_{1, \alpha, \beta'}$ have same cycle invariant and opposite sign invariant

Figure 25.  Left: a permutation $\sigma$. Right : the permutation $\sigma _i(C_p)$

Figure 26.  The base cases of the induction of the proof of proposition 58

Figure 27.  Left: a permutation with a $C_p$ structure containing two even cycles of even length. Middle and Right: By proposition 53 the two permutations have same cycle invariant and opposite sign

Figure 28.  Two families of base permutations with their respective cycle invariant

Figure 29.  The permutation resulting from adding a $C_p$ on the last edge of $\sigma ^0$ or one of its successors. It is clearly also $I_2X$

Figure 30.  The two constructed $I_2X$-permutations $\sigma _1 = \sigma _{|\sigma |}(C_p)$ and $\sigma '_1 = \sigma _{|\sigma |}(C_{p-(2), 2})$ with invariant $(\lambda , r, \pm s)$. In this case $p = 4k+1$

Figure 31.  The scheme to add two different even cycles to a permutation

Figure 32.  Two families of $I_2X$-permutations with their respective cycle invariant

Figure 33.  The case $\sigma$ has type $X(r, i)$ of lemma 68. We have $\sigma _1 = \tau_{1, \alpha_1 = 1, \beta} = \tau_{1, t^{rk}_0, b^{rk}_{i\!-\!1}}$

Figure 34.  The case $\sigma$ has type $H(i, r_2)$ of lemma 69. We have $\sigma _1 = \tau_{1, \alpha_1 = 1, \beta} = \tau_{1, t^{rk}_0, b_{i-1, i\!-\!1, 1}}$

Figure 35.  The construction of the proof of the lemma. We have $\sigma _1 = \tau_{1, 1, \beta'}$, $\sigma _1' = \tau_{1, 1, \beta}$ and $\sigma _1 = B(S)(\sigma _1)$ moreover ${\bar A}(\tau) = \pm 2^{\frac{n}{2}}$

Figure 36.  The construction of the proof of the lemma 73. Both $\sigma$ and $\sigma _{next}$ have type $X(r, i)$ and ${\bar A}(d(\sigma )) = -{\bar A}(d(\sigma _{next}))$

Figure 37.  $(\sigma '_4, \sigma '_2)$ are both permutations with invariant $(\lambda , r, s\neq 0)$ and $\tau_2$ has sign invariant 0. However proposition 19 applied to $\sigma '_4, \sigma '_2$ and $\tau_2$ implies that $\sigma '_4$ should have invariant $-s$, This is contradictory and thus the case $\Pi'''_b(\beta) = b_{0, i-1, 1}$ cannot happen

Figure 38.  $\sigma$ and $\sigma '$ are standard of type $X(r, i)$. The labels of the principal cycle of $\sigma$ are send to the arcs of the principal cycle of $\sigma '$ by the sequence $R^{-1}B(S)R$. Indeed they are attached to the $i$th first labels of the rank of $\tau$ and the labels of the rank are fixed. Thus they are also attached to $i$th first the labels of the rank of $\tau'$ which are the arcs of the principal cycle of $\sigma '$.
In the figure, we choose $\Pi_t(\alpha) = t_{0, i, j}$ instead of $t_{c, i, j}$ for some $c$ for space-saving purpose

Figure 39.  The case of the cycle 1-shift. We apply proposition 28 on $\sigma '$ and $\sigma$

Figure 40.  The case of the cycle jump. We apply proposition 76 on $\sigma '$ and $\sigma$

Figure 41.  The case of the cycle 2-shift. We apply proposition 28 on $\sigma '$ and $\sigma$

Figure 42.  Description of the structure of configurations in the identity class ${\rm{Id}}_n$, besides the configuration ${\rm{id}}_n$

Table 1.  Cycle, rank and sign invariants of the exceptional classes. The sign $s \in \{-1, 0, +1\}$ is shortened into $\{-, 0, +\}$ Table 2.  List of invariants $(\lambda , r, s)$ for $n \leq 8$, for which the corresponding class in the $\mathcal{S}_n$ dynamics exist. We shorten $s$ to $\{-, +\}$ if valued $\{-1, +1\}$, and omit it if valued 0 Table 3.  Modification to the cycle invariant between $\sigma$ and $\sigma |_{1, 0, i}$, for every possible $i$. In green, the newly-added edge. In red, parts that get added to the rank path. In blue, parts which are singled out to form a new cycle • Figures(42)

Tables(3)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint