Valérie Berthé (CNRS et Institut de recherche en informatique fondamentale)
Titre : Mots, fractions continues et arbres
Résumé : L’étude des mots sturmiens et de leurs systèmes dynamiques symboliques associés est intimement liée à celle des suites de Kronecker et des fractions continues usuelles. L’interaction fonctionne dans les deux directions : une approche arithmétique permet de décrire les propriétés dynamiques et symboliques de ces mots, mais inversement, l’étude des mots sturmiens permet de déduire des propriétés arithmétiques, par exemple de discrépance. Nous montrons comment étendre ces interactions via l’étude d’une famille de mots infinis qui englobe, en particulier, les sturmiens, mais aussi les codages d’échanges d’intervalles. Ces mots sont définis en termes de graphes d’extension permettant de décrire leurs langages : ces graphes sont des arbres. Nous montrons comment en déduire des développements en fractions continues généralisés et leurs propriétés arithmétiques.

Jehanne Dousse (Université de Zurich, Suisse)
Titre : Enumeration exacte et asymptotique des partitions d'entiers
Résumé : Une partition d'un entier positif n est une suite décroissante d'entiers dont la somme est n. Bien que leur définition soit très simple, les partitions sont très difficiles à compter et aucune formule simple n'est connue pour leur nombre. Cependant, il est possible d'obtenir de belles formules asymptotiques. Cette approche a été initiée par Hardy et Ramanujan avec leur méthode du cercle, qui repose sur la modularité de la série génératrice des partitions. Dans la première partie de l'exposé, j'expliquerai leur méthode ainsi qu'une généralisation aux formes de Jacobi. Une autre approche est de montrer que différents ensemble de partitions ont exactement la même cardinalité. Par exemple pour tout n, le nombre de partitions de n en parts impaires est égal au nombre de partitions de n en parts distinctes. Dans la deuxième partie de la présentation, je discuterai de ces identités -dont certaines viennent de la théorie des représentations- et je présenterai une nouvelle méthode pour les raffiner et les généraliser.

Michel Habib (Institut de recherche en informatique fondamentale)
Titre : Graph Searches on Structured Families of Graphs and Matrices
Résumé : Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS). Many classes of graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently such vertex orderings. These orderings expose structure that we exploit to develop efficient linear and near-linear time algorithms for some NP-hard problems (independent set, colouring, Hamiltonicity for instance). In particular, we will prove fixed point type theorems for LexBFS, and then focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs. Then I will present the relationships between graph searches, graph geometric convexities and antimatroids.
To finish I will present some recent results about Robinsonian matrices by M. Laurent and M. Seminaroti and their relationships with graph searches. This yields a new area of research to investigate.

Clemens Heuberger (Université de Klagenfurt, Autriche)
Titre : Analysis of Sequences using Transducer Automata
Résumé : This talk focusses on sequences which can be generated by transducer automata. Such sequences frequently occur in the context of digit problems, for instance in the design of efficient scalar multiplication algorithms used in elliptic curve cryptography. Existence and optimality questions can be decided by connectivity properties of the graphs underlying the corresponding transducers and precise asymptotic results can be obtained.

Florent Jouve (Université de Bordeaux)
Titre : Un crible pour les graphes de Cayley
Résumé : Dans divers contextes récents (crible pour les orbites de Bourgain-Gamburd-Sarnak, théorie de Galois probabiliste dans les groupes arithmétiques,...) des formes traditionnelles de crible (crible de Brun, grand crible) ont été utilisées pour des groupes généraux dans le but de quantifier la probabilité que certaines propriétés que l'on pense rarement vérifiées soient satisfaites. Un point commun à ces travaux est le rôle joué par certaines familles de graphes expanseurs provenant de certains quotients finis des groupes intervenant. Celles-ci fournissent en effet une propriété d'écart spectral nécessaire à la mise en oeuvre du crible. Je présenterai un travail commun avec J.-S. Sereni où l'on propose une forme de crible dans un contexte abélien assez général se basant sur le fait que certaines familles de graphes de Cayley "aléatoires" forment de bons expanseurs. On illustrera la méthode sur quelques exemples simples.

Manon Stipulanti (Université de Liège, Belgique)
Titre : Triangles de Pascal et de Sierpinski étendus aux coefficients binomiaux de mots
Résumé : Le coefficient binomial $\binom{u}{v}$ de deux mots $u$ et $v$ est défini comme le nombre de fois que $v$ apparaît comme sous-suite du mot $u$. Par exemple, $\binom{abbab}{ab}=4$. Il étend de manière naturelle le coefficient binomial de deux entiers. Ce concept a été largement étudié depuis plus d'une trentaine d'années (cf. par exemple, les travaux de Simon et Sakarovitch). Dans cet exposé, je parlerai des recherches effectuées dans le cadre de ma thèse sur une extension des triangles de Pascal et de Sierpinski à ces coefficients.