Set of periods, topological entropy and combinatorial dynamics for tree and graph maps

La tesi versa sobre sistemes dinàmics discrets 1-dimensionals, des d'un punt de vista combinatori i topològic. Estem interessats en les òrbites periòdiques i l'entropia topològica de les aplicacions contínues definides en arbres i grafs.El problema central és la caracterització del conjunt de períodes de totes les òrbites periòdiques d'una aplicació contínua d'un arbre en ell mateix. El teorema de Sharkovskii (1964) fou el primer resultat remarcable en aquest sentit. Aquest bonic teorema estableix que el conjunt de períodes d'una aplicació de l'interval és un segment inicial d'un ordre lineal (ordre de Sharkovskii). Recíprocament, donat qualsevol segment inicial d'aquest ordre, existeix una aplicació de l'interval que el té com a conjunt de períodes. Durant les darreres dècades hi ha hagut diversos intents de trobar resultats similars al de Sharkovskii per a altres espais 1-dimensionals. Recentment, el cas d'arbres ha estat tractat especialment. El Teorema de Baldwin (1991) resol el problema en el cas de les n-estrelles i ha estat un dels avenços més significatius en aquesta direcció. Aquest resultat estableix que el conjunt de períodes per a una aplicació de la n-estrella és unió finita de segments inicials de n ordres parcials (ordres de Baldwin), i recíprocament.El nostre objectiu principal és descriure l'estructura del conjunt de períodes de qualsevol aplicació contínua d'un arbre T en termes de les propietats combinatòries i topològiques de T: quantitat i disposició d'extrems, vèrtexs i arestes. En el capítol 1 discutim detalladament la manera més natural d'atacar el problema, i proposem una estratègia consistent en tres etapes consecutives. L'eina principal d'aquesta estratègia són els models minimals de patrons. Aquestes nocions es van desenvolupar i utilitzar durant les darreres dècades en el context de l'interval. En canvi, no es disposava de definicions operatives equivalents per a arbres, fins que al 1997 Alseda, Guaschi, Los, Manyosas i Mumbru proposaren de definir el patró d'un conjunt finit invariant P essencialment com una classe d'homotopia d'aplicacions relativa a P, i provaren (constructivament) que sempre existeix un model P-canònic amb propietats de minimalitat dinàmica. L'objectiu del capítol 2 és implementar completament el programa proposat, duent a terme les etapes 2 i 3. El resultat principal d'aquest capítol diu que, donada una aplicació g definida en un arbre T, existeix un conjunt S de successions finites d'enters positius tal que el conjunt de períodes de g és (excepte un conjunt finit explícitament acotat) una unió finita de segments inicials d'ordres de Baldwin donats en termes del conjunt S, que depèn de les propietats combinatòries de l'arbre T. També provem el recíproc. En el capítol 3 duem a terme experiments informàtics sobre la minimalitat dinàmica dels models canònics. En un esperit de programació modular, hem dissenyat moltes funcions autocontingudes que poden ser usades per implementar una gran varietat d'aplicacions d'ús divers. Entre altres, tenim funcions que calculen el model canònic d'un patró donat per l'usuari, calculen la matriu de Markov associada a un model monòton a trossos i extreuen tots els llaços simples d'una matriu de transició de Markov. Finalment, en el capítol 4 generalitzem alguns resultats de Block i Coven, Misiurewicz i Nitecki i Takahashi, en els quals l'entropia topològica d'una aplicació de l'interval s'aproxima per les entropies de les seves òrbites periòdiques. Hem provat relacions anàlogues en el context de les aplicacions de grafs.This memoir deals with one-dimensional discrete dynamical systems, from both a topological and a combinatorial point of view. We are interested in the periodic orbits and topological entropy of continuous self-maps defined on trees and graphs.The central problem is the characterisation of the set of periods of all periodic orbits exhibited by any continuous map from a tree into itself. The Sharkovskii's Theorem (1964) was the first remarkable result in this setting. This theorem states that the set of periods of any interval map is an initial segment of a linear ordering (the so-called Sharkovskii ordering). Conversely, given any initial segment of the Sharkovskii ordering, there exists an interval map whose set of periods coincides with it.During the last decades there have been several attempts to find results similar to that of Sharkovskii for other one-dimensional spaces. Recently, the case of maps defined on general trees has been specially treated. Baldwin's Theorem (1991), which solves the problem in the case of n-stars for any n, has been one of the most significant advances in this direction. This result states that the set of periods of any n-star map is a finite union of initial segments of n-many partial orderings (the Baldwin orderings). The converse is also true.Our main purpose is to describe the generic structure of the set of periods of any continuous self-map defined on a tree T in terms of the combinatorial and topological properties of T: amount and arrangement of endpoints, vertices and edges. In Chapter 1 we make a detailed discussion about which is the more natural approach to this problem, and we propose a strategy consisting on three consecutive stages and using minimal models of patterns as the main tool. These notions were developed in the context of interval maps and widely used in a number of papers during the last two decades. However, equivalent operative definitions for tree maps were not available until 1997, when Alseda, Guaschi, Los, Manosas and Mumbru proposed to define the pattern of a finite invariant set P essentially as a homotopy class of maps relative to the points of P, and proved (constructively) that there always exists a P-canonical model displaying dynamic minimality properties.The goal of Chapter 2 is to implement in full the above programme by completing stages 2 and 3. The main result of Chapter 2 tells us that for each tree map g defined on a tree T there exists a finite set S of sequences of positive integers such that the set of periods of g is (up to an explicitly bounded finite set) a finite union of initial segments of Baldwin orderings, given in terms of the set S, which depends on the combinatorial properties of the tree T. We also prove the converse result.In Chapter 3 we report some computer experiments on the minimality of the dynamics of canonical models. In a spirit of modular programming, we have designed lots of self-contained functions which can be used to implement a wide variety of several-purpose software. Among other, we have functions that: compute the canonical model of a pattern provided by the user, calculate the Markov transition matrix associated to a piecewise monotone tree map and extract all the simple loops of a given length from a Markov transition matrix.Finally, in Chapter 4 we generalize some results of Block & Coven, Misiurewicz & Nitecki and Takahashi, where the topological entropy of an interval map was approximated by the entropies of its periodic orbits. We prove analogous relations in the setting of graph maps