Name
Abstract | ||
|---|---|---|
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 @C(G) denote the smallest set of trees of relations containing G and invariant under induction. The induction mapping allows us to endow @C(G) with the structure of a connected directed graph, which we call the graph of graphs. We investigate the structure of @C(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 @C(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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.ejc.2011.05.002 | Eur. J. Comb. |
Keywords | Field | DocType |
circular order,interval exchange transformation,combinatorial point,combinatorial object,tree structure,catalan number,combinatorial tree,abstract secondary structure,induction mapping,relations g,complete characterization,interesting combinatorial property,genetics,secondary structure,directed graph,number theory,ergodic theory,cluster algebra | Discrete mathematics,Combinatorics,Polygon,Catalan number,Ergodic theory,Directed graph,Cardinality,Cluster algebra,Tree structure,Invariant (mathematics),Mathematics | Journal |
Volume | Issue | ISSN |
32 | 8 | 0195-6698 |
Citations | PageRank | References |
2 | 0.67 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julien Cassaigne | 1 | 282 | 40.80 |
| Sébastien Ferenczi | 2 | 61 | 10.74 |
| Luca Q. Zamboni | 3 | 253 | 27.58 |