A connected digraph in which the in-degree of any vertex equals its out-degree is Eulerian; this baseline result is used as the basis of existence proofs for universal cycles (also known as ucycles or generalized deBruijn cycles or U-cycles) of several combinatorial objects. The existence of ucycles is often dependent on the specific representation that we use for the combinatorial objects. For example, should we represent the subset {2,5} of {1,2,3,4,5} as “25” in a linear string? Is the representation “52” acceptable? Or is it tactically advantageous (and acceptable) to go with {0,1,0,0,1}? In this paper, we represent combinatorial objects as graphs, as in [3], and exhibit the flexibility and power of this representation to produce graph universal cycles, or Gucycles, for k-subsets of an n-set; permutations (and classes of permutations) of [n]={1,2,…,n}, and partitions of an n-set, thus revisiting the classes first studied in [5]. Under this graphical scheme, we will represent {2,5} as the subgraph A of C5 with edge set consisting of {2,3} and {5,1}, namely the “second” and “fifth” edges in C5. Permutations are represented via their permutation graphs, and set partitions through disjoint unions of complete graphs.

For many combinatorial objects we can associate a natural probability distribution on the members of the class, and we can then call the resulting class a class of random structures. Random structures form good models of many real world problems, in particular real networks and disordered media. For many such problems, the systems under consideration can be very large, and we often care about whether a property holds most of the time. In particular, for a given class of random structures, we say that a property holds with high probability if the probability that that property holds tends to one as the size of the structures increase. We examine several classes of random structures with real world applications, and look at some properties of each that hold with high probability. First we look at percolation in 3 dimensional lattices, giving a method for producing rigorous confidence intervals on the percolation threshold. Next we look at random geometric graphs, first examining the connectivity thresholds of nearest neighbour models, giving good bounds on the threshold for a new variation on these models useful for modelling wireless networks, and then look at the cop number of the Gilbert model. Finally we look at the structure of random sum-free sets, in particular examining what the possible densities of such sets are, what substructures they can contain, and what superstructures they belong to.

A l’opposé de l’approche consistant à concevoir aucas par cas des contraintes et des algorithmes leur étant dédiés, l’objet de cette thèse concerne d’une part la description de familles de contraintes en termes de composition de fonctions, et d’autre part la synthèse d’objets combinatoires pour de telles contraintes. Les objets concernés sont des bornes précises, des coupes linéaires, des invariants non-linéaires et des automates finis ; leur but principal est de prendre en compte l’aspect combinatoire d’une seule contrainte ou d’une conjonction de contraintes. Ces objets sont obtenus d’une façon systématique et sont paramétrés par une ou plusieurs contraintes, par le nombre de variables dans une séquence, et par les domaines initiaux de ces variables. Cela nous permet d’obtenir des objets indépendants d’une instance considérée. Afin de synthétiser des objets combinatoires nous tirons partie de la vue déclarative de telles contraintes, basée sur les expressions régulières, ainsi que la vue opérationnelle, basée sur les automates à registres et les transducteurs finis. Il y a plusieurs avantages à synthétiser des objets combinatoires par rapport à la conception d’algorithmes dédiés : 1) on peut utiliser ces formules paramétrées dans plusieurs contextes, y compris la programmation par contraintes et la programmation linéaire, ce qui est beaucoup plus difficile avec des algorithmes ; 2) la synergie entre des objets combinatoires nous donne une meilleure performance en pratique ; 3) les quantités calculées par certaines des formules peuvent être utilisées non seulement dans le contexte de l’optimisation mais aussi pour la fouille de données. / Contrary to the standard approach consisting in introducing ad hoc constraints and designing dedicated algorithms for handling their combinatorial aspect, this thesis takes another point of view. On the one hand, it focusses on describing a family of sequence constraints in a compositional way by multiple layers of functions. On the other hand, it addresses the combinatorial aspect of both a single constraint and a conjunction of such constraints by synthesising compositional combinatorial objects, namely bounds, linear inequalities, non-linear constraints and finite automata. These objects are obtained in a systematic way and are not instance-specific: they are parameterised by one or several constraints, by the number of variables in a considered sequence of variables, and by the initial domains of the variables. When synthesising such objects we draw full benefit both from the declarative view of such constraints, based on regular expressions, and from the operational view, based on finite transducers and register automata.There are many advantages of synthesising combinatorial objects rather than designing dedicated algorithms: 1) parameterised formulae can be applied in the context of several resolution techniques such as constraint programming or linear programming, whereas algorithms are typically tailored to a specific technique; 2) combinatorial objects can be combined together to provide better performance in practice; 3) finally, the quantities computed by some formulae cannot just be used in an optimisation setting, but also in the context of data mining.