Combinatorial trees arising in the study of interval exchange transformations

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.