×

Combinatorial trees arising in the study of interval exchange transformations. (English) Zbl 1232.05192

Summary: 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 S. Ferenczi and L. Q. Zamboni [J. Anal. Math. 112, 289–328 (2010; Zbl 1225.37003)] 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 [S. Ferenczi and L. Q. Zamboni, J. Anal. Math. 112, 289–328 (2010; Zbl 1225.37003)]. In a recent sequel to this paper, Marsh and Schroll have established interesting connections to the theory of cluster algebras and polygonal triangulations [R. Marsh and S. Schroll, “RNA secondary structures, polygon dissections and clusters”, arXiv:1010.3763]. For each tree of relations \(G\), we let \(\varGamma (G)\) denote the smallest set of trees of relations containing \(G\) and invariant under induction. The induction mapping allows us to endow \(\varGamma (G)\) with the structure of a connected directed graph, which we call the graph of graphs. We investigate the structure of \(\varGamma (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 \(\varGamma (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.

MSC:

05C75 Structural characterization of families of graphs
05C05 Trees
05C90 Applications of graph theory
92D10 Genetics and epigenetics

Citations:

Zbl 1225.37003

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brown, G. W., Enumerations of triangulations of the disk, Proc. London Math. Soc., 14, 3, 746-768 (1964) · Zbl 0134.19503
[2] Condon, A., Problems on RNA secondary structure prediction and design, (Automata, Languages and Programming. Automata, Languages and Programming, Lecture Notes in Comput. Sci., vol. 2719 (2003)), 22-32 · Zbl 1060.68634
[3] Ferenczi, S.; Zamboni, L. Q., Structure of k-interval exchange transformations: induction, trajectories, and distance theorems, J. Anal. Math., 112, 289-328 (2010) · Zbl 1225.37003
[4] Ferenczi, S.; Zamboni, L. Q., Eigenvalues and simplicity of interval exchange transformations, Ann. Sci. Ec. Norm. Sup., 44, 4, 361-392 (2011) · Zbl 1237.37010
[5] R. Marsh, S. Schroll, RNA secondary structures, polygon dissections and clusters, preprint arXiv:1010.3763v1; R. Marsh, S. Schroll, RNA secondary structures, polygon dissections and clusters, preprint arXiv:1010.3763v1
[6] N.J.A. Sloane, The On-line Encyclopedia of Integer Sequences; see http://www.research.att.com/njas/sequences/; N.J.A. Sloane, The On-line Encyclopedia of Integer Sequences; see http://www.research.att.com/njas/sequences/ · Zbl 1274.11001
[7] Torkildsen, H. A., Counting cluster-tilted algebras of type \(A_n\), Int. Electron. J. Algebra, 4, 149-158 (2008) · Zbl 1163.16011
[8] Vance, B., Counting ordered trees by permuting their parts, Amer. Math. Monthly, 113, 329-335 (2006) · Zbl 1104.05006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.