In recent years it has been shown that the folding pattern of an RNA molecule plays an important role in its function, likened to a lock and key system. γ-structures are a subset of RNA pseudoknot structures filtered by topological genus that lend themselves nicely to combinatorial analysis. Namely, the coefficients of their generating function can be approximated for large n. This paper is an investigation into the length-spectrum of the longest block in random γ-structures. We prove that the expected length of the longest block is on the order n - O(n^1/2). We further compare these results with a similar analysis of the length-spectrum of rainbows in RNA secondary structures, found in Li and Reidys (2018). It turns out that the expected length of the longest block for γ-structures is on the order the same as the expected length of rainbows in secondary structures. / Master of Science / Ribonucleic acid (RNA), similar in composition to well-known DNA, plays a myriad of roles within the cell. The major distinction between DNA and RNA is the nature of the nucleotide pairings. RNA is single stranded, to mean that its nucleotides are paired with one another (as opposed to a unique complementary strand). Consequently, RNA exhibits a knotted 3D structure. These diverse structures (folding patterns) have been shown to play important roles in RNA function, likened to a lock and key system. Given the cost of gathering data on folding patterns, little is known about exactly how structure and function are related. The work presented centers around building the mathematical framework of RNA structures in an effort to guide technology and further scientific discovery. We provide insight into the prevalence of certain important folding patterns.

There has been much recent interest in random graphs sampled uniformly from the set of (labelled) graphs on n vertices in a suitably structured class A. An important and well-studied example of such a suitable structure is bridge-addability, introduced in 2005 by McDiarmid et al. in the course of studying random planar graphs. A class A is bridge-addable when the following holds: if we take any graph G in A and any pair u,v of vertices that are in different components in G, then the graph G′ obtained by adding the edge uv to G is also in A. It was shown that for a random graph sampled from a bridge-addable class, the probability that it is connected is always bounded away from 0, and the number of components is bounded above by a Poisson law. What happens if ’bridge-addable’ is replaced by something weaker? In this thesis, this question is explored in several different directions. After an introductory chapter and a chapter on generating function methods presenting standard techniques as well as some new technical results needed later, we look at minor-closed, labelled classes of graphs. The excluded minors are always assumed to be connected, which is equivalent to the class A being decomposable - a graph is in A if and only if every component of the graph is in A. When A is minor-closed, decomposable and bridge-addable various properties are known (McDiarmid 2010), generalizing results for planar graphs. A minor-closed class is decomposable and bridge-addable if and only if all excluded minors are 2-connected. Chapter 3 presents a series of examples where the excluded minors are not 2-connected, analysed using generating functions as well as techniques from graph theory. This is a step towards a classification of connectivity behaviour for minor-closed classes of graphs. In contrast to the bridge-addable case, different types of behaviours are observed. Chapter 4 deals with a new, more general vari- ant of bridge-addability related to edge-expander graphs. We will see that as long as we are allowed to introduce ’sufficiently many’ edges between components, the number of components of a random graph can still be bounded above by a Pois- son law. In this context, random forests in Kn,n are studied in detail. Chapter 5 takes a different approach, and studies the class of labelled forests where some vertices belong to a specified stable set. A weighting parameter y for the vertices belonging to the stable set is introduced, and a graph is sampled with probability proportional to y*s where s is the size of its stable set. The behaviour of this class is studied for y tending to ∞. Chapters 6 concerns random graphs sampled from general decomposable classes. We investigate the minimum size of a component, in both the labelled and the unlabelled case.

Le but de cette thèse est d'établir des résultats énumératifs sur certaines classes de chemins et d'animaux. Ces résultats sont obtenus en appliquant la théorie des empilements de pièces développée par Viennot. Nous étudions les excursions discrètes (ou chemins de Dyck généralisés) de hauteur bornée; nous obtenons des résultats énumératifs qui interprètent combinatoirement et étendent des résultats de Banderier, Flajolet et Bousquet-Mélou. Nous décrivons et énumérons plusieurs classes de chemins auto-évitants, dits chemins faiblement dirigés. Ces chemins sont plus nombreux que les chemins prudents qui forment la classe naturelle la plus grande jusqu'alors. Nous calculons le périmètre de site moyen des animaux dirigés, prouvant des conjectures de Conway et Le Borgne. Enfin, nous obtenons des résultats nouveaux sur l'énumération des animaux de Klarner et les animaux multi-dirigés de Bousquet-Mélou et Rechnitzer. / The goal of this thesis is to prove enumerative results on some classes of lattice walks and animals. These results are applications of the theory of heaps of pieces developed by Viennot. We study discrete excursions (or generalized Dyck paths) with bounded height; we obtain enumerative results that give a combinatorial interpretation and extend results by Banderier, Flajolet and Bousquet-Mélou. We describe and enumerate several classes of self-avoiding walks called weakly directed walks. These classes are larger than the class of prudent walks, the largest natural class enumerated so far. We compute the average site perimeter of directed animals, proving conjectures by Conway and Le Borgne. Finally, we obtain new results on the enumeration of Klarner animals and multi-directed animals defined by Bousquet-Mélou and Rechnitzer.

Un programme concurrent est composé de plusieurs unités logiques : les processus. Chaque processus a un comportement qui lui est propre : il exécute ses actions de façon séquentielle. Un objectif important est de s'assurer que de tels systèmes concurrents complexes soient cependant exempts de défaut. Cette problématique est étudiée dans le cadre de la théorie de la concurrence. Quand plusieurs processus s’exécutent en parallèle, l’ordre d’exécution des actions du programme global n’est plus déterminé. On assiste au fameux phénomène "d’explosion combinatoire" faisant référence au très grand nombre d’exécutions globales possibles. Les diverses techniques et méthodes d'analyse existantes (model checking, analyse statique, tests automatisés, etc) se heurtent irrémédiablement à cette "explosion". Cette thèse s'inscrit dans un projet à long terme d'étude quantitative de ce phénomène et de développement des techniques d’analyse statistique basées sur la génération aléatoire uniforme. Notre objectif dans cette thèse est de traiter une composante fondamentale de la concurrence : la synchronisation. Ce mécanisme permet aux processus de communiquer entre eux. Dans cette thèse nous proposons un modèle combinatoire de structures croissantes pour modéliser les exécutions de programmes concurrents synchronisés. Avec des outils de combinatoire analytique nous obtenons plusieurs résultats exacts et asymptotiques sur le nombre moyen d'exécutions dans des sous-classes de programmes concurrents. Nous présentons aussi plusieurs algorithmes de génération aléatoire uniforme de structures croissantes et de leurs étiquetages. / A concurrent program is a composition of several logical blocks: the processes. Each process has its own behavior, independent from the others: it sequentially runs its actions. An important goal is to ensure that such concurrent complex systems are faultless. This problem is studied in the field of concurrency theory. When several process are running in parallel, the running order of the actions of the total program is no more decided. This is the well-known "combinatorial explosion" phenomena, meaning that the number of possible runs of the global program is huge. The analysis techniques and methods existing (model checking, static analysis, automated testing, etc) are irremediably limited by this "explosion". This thesis is a part of a long-term project about the quantitative study of this phenomena and the development of statistic analysis methods based on the uniform random generation. Our specific goal is to study a fundamental principle of the concurrency theory: the synchronization. This mechanism allows communications between the processes. In this thesis we propose a combinatorial model of increasingly labeled structures to deal with runs of synchronized concurrent programs. Using the tools of analytic combinatorics we obtain close formulas and asymptotic equivalents for the average number of runs in several subclasses of concurrent programs. We also present algorithms of uniform random generation of increasingly labeled structures and for their increasing labelings.

No description available.

Cette thèse se compose de plusieurs travaux portant sur l'énumération et le comportement asymptotique de structures combinatoires apparentées aux partitions d'entiers. Un premier travail s'intéresse aux partitions d'entiers bipartites, qui constituent une généralisation bidimensionnelle des partitions d'entiers. Des équivalents du nombre de partitions sont obtenus dans le régime critique où l'un des entiers est de l'ordre du carré de l'autre entier et au delà de ce régime critique. Ceci complète les résultats établis dans les années cinquante par Auluck, Nanda et Wright. Le deuxième travail traite des chaînes polygonales à sommets entiers dans le plan. Pour un modèle statistique introduit par Sinaï, une représentation intégrale exacte de la fonction de partition est donnée. Ceci conduit à un équivalent du nombre de chaînes joignant deux points distants qui fait intervenir les zéros non triviaux de la fonction zêta de Riemann. Une analyse combinatoire détaillée des chaînes convexes est présentée. Elle permet de montrer l'existence d'une forme limite pour les chaînes convexes aléatoires ayant peu de sommets, répondant ainsi à une question ouverte de Vershik. Un troisième travail porte sur les zonotopes à sommets entiers en dimension supérieure. Un équivalent simple est donné pour le logarithme du nombre de zonotopes contenus dans un cône convexe et dont les extrémités sont fixées. Une loi des grands nombres est établie et la forme limite est caractérisée par la transformée de Laplace du cône. / This thesis consists of several works dealing with the enumeration and the asymptotic behaviour of combinatorial structures related to integer partitions. A first work concerns partitions of large bipartite integers, which are a bidimensional generalization of integer partitions. Asymptotic formulæ are obtained in the critical regime where one of the numbers is of the order of magnitude of the square of the other number, and beyond this critical regime. This completes the results established in the fifties by Auluck, Nanda, and Wright. The second work deals with lattice convex chains in the plane. In a statistical model introduced by Sinaï, an exact integral representation of the partition function is given. This leads to an asymptotic formula for the number of chains joining two distant points, which involves the non trivial zeros of the Riemann zeta function. A detailed combinatorial analysis of convex chains is presented. It makes it possible to prove the existence of a limit shape for random convex chains with few vertices, answering an open question of Vershik. A third work focuses on lattice zonotopes in higher dimensions. An asymptotic equality is given for the logarithm of the number of zonotopes contained in a convex cone and such that the endings of the zonotope are fixed. A law of large numbers is established and the limit shape is characterized by the Laplace transform of the cone.