Combinatorial trees arising in the study of interval exchange transformations - Institut de Mathématiques de Luminy Accéder directement au contenu
Article Dans Une Revue European Journal of Combinatorics Année : 2011

Combinatorial trees arising in the study of interval exchange transformations

Résumé

In this paper we study a new class of combinatorial objects that we call trees of relations equipped with an operation that we call induction. These trees were first introduced in Ferenczi and Zamboni (2010) [3] in the context of interval exchange transformations but they may be studied independently from a purely combinatorial point of view. They possess a variety of interesting combinatorial properties and have already been linked to a number of different areas including ergodic theory and number theory—see Ferenczi and Zamboni (2010, in press) [3,4]. In a recent sequel to this paper, Marsh and Schroll have established interesting connections to the theory of cluster algebras and polygonal triangulations: Marsh and Schroll (2010) [5]. For each tree of relations G, we let Γ (G) denote the smallest set of trees of relations containing G and invariant under induction. The induction mapping allows us to endow Γ (G) with the structure of a connected directed graph, which we call the graph of graphs. We investigate the structure of Γ (G) and define a circular order based on the tree structure which turns out to be a complete invariant for the induction mapping. This gives a complete characterization of Γ (G) which allows us to compute its cardinality in terms of Catalan numbers. We show that the circular order also defines an abstract secondary structure similar to one occurring in genetics in the study of RNA.
Fichier principal
Vignette du fichier
cfz2.pdf (172.09 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01265525 , version 1 (03-02-2016)

Identifiants

Citer

Julien Cassaigne, Sébastien Ferenczi, Luca Q. Zamboni. Combinatorial trees arising in the study of interval exchange transformations. European Journal of Combinatorics, 2011, 32, ⟨10.1016/j.ejc.2011.05.002⟩. ⟨hal-01265525⟩
408 Consultations
114 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More