Les récurrences diviser pour régner, qui fréquemment relient les valeurs d'une suite en un entier et sa moitié, tirent leur nom de la stratégie diviser pour régner communément employée en algorithmique. Mais elles apparaissent aussi dans des problèmes de dénombrement liés à la combinatoire des mots ou à la combinatoire des partitions, ou encore en lien avec les séries algébriques à coefficients dans un corps fini, voire de manière inattendue dans des questions d'optimisation. Leur aspect exotique et les différentes formes qu'elles peuvent prendre leurs confèrent un aspect déroutant et nous montrons comment il est possible de les appréhender. L'analyse combinatoire, l'analyse d'algorithmes font étudier le comportement asymptotique des solutions de ces récurrences. Nous envisageons différentes approches depuis les plus élémentaires jusqu'au plus sophistiquées, utilisant au choix l'algèbre linéaire, la théorie analytique des nombres ou la théorie des probabilités.

Les processus de fragmentation sont des modèles aléatoires pour décrire l'évolution d'objets (particules, masses) sujets à des fragmentations successives au cours du temps. L'étude de tels modèles remonte à Kolmogorov, en 1941, et ils ont depuis fait l'objet de nombreuses recherches. Ceci s'explique à la fois par de multiples motivations (le champs d'applications est vaste : biologie et génétique des populations, formation de planètes, polymérisation, aérosols, industrie minière, informatique, etc.) et par la mise en place de modèles mathématiques riches et liés à d'autres domaines bien développés en Probabilités, comme les marches aléatoires branchantes, les processus de Lévy et les arbres aléatoires. L'objet de ce mini-cours est de présenter les processus de fragmentation auto-similaires, tels qu'introduits par Bertoin au début des années 2000s. Ce sont des processus markoviens, dont la dynamique est caractérisée par une propriété de branchement (différents objets évoluent indépendamment) et une propriété d'auto-similarité (un objet se fragmente à un taux proportionnel à une certaine puissance fixée de sa masse). Nous discuterons la construction de ces processus (qui incluent des modèles avec fragmentations spontanées, plus délicats à construire) et ferons un tour d'horizon de leurs principales propriétés.

Les déterminants jouent un rôle important dans plusieurs domaines de l'énumération, notamment dans l'énumération de pavages et de chemins, les deux étant fortement liées. Le but de ce cours sera, premièrement, de donner un survol des résultats et techniques qui sont disponibles, et, deuxièmement, de faire une introduction au programme de «modélisation d'électrostatique à l'aide des pavages en losanges» initié par Mihai Ciucu.

Les chaînes de Markov à mémoire de longueur variable constituent une classe de sources probabilistes. Il sera question dans cet exposé d’existence et unicité de mesure invariante pour une collection d’exemples de chaînes. Nous nous intéresserons également au comportement asymptotique d’une marche aléatoire dont les longueurs de sauts ne sont pas forcément intégrables. Les lois de sauts dépendent partiellement du passé de la trajectoire. Plus précisément, la probabilité de monter ou de descendre dépend du temps passé dans la direction dans laquelle le marcheur est en train d’avancer. Un critère de récurrence/transience s’exprimant en fonction des paramètres du modèle sera énoncé. Suivront plusieurs exemples illustrant le caractère instable du type de la marche lorsqu’on perturbe légèrement les paramètres. Les travaux décrits dans cet exposé ont été faits en collaboration avec B. Chauvin, F. Paccaut et N. Pouyanne ou B. de Loynes, A. Le Ny et Y. Offret.

Encore loin des canons académiques, de nombreux produits cryptographiques en usage aujourd'hui utilisent encore le systèmes RSA dont la sécurité repose sur la difficulté présumée de factoriser les entiers. Le meilleur algorithme connu pour s'attaquer à ce problème est le crible algébrique où la notion de nombre friable joue un rôle crucial. De nature profondément probabiliste, cet algorithme repose sur des structures aléatoires qui ne sont pas traitées de manière très satisfaisante dans les implémentations actuelles, alors que cela pourrait améliorer directement le temps de calcul ou bien faciliter la modélisation et la simulation pour mieux estimer la sécurité des clefs. L'objectif de cet exposé est de décrire les grandes lignes de l'algorithme du crible algébrique, et d'expliquer la nature des problèmes où une vision "aléatoire" pourrait être fructueuse.

Après avoir expliqué la notion de Z-invariance pour les modèles de mécanique statistique, nous introduisons une famille à un paramètre (dépendant du module elliptique) de Laplaciens massiques Z-invariants définis sur les graphes isoradiaux. Nous démontrons une formule explicite pour son inverse, la fonction de Green massique, qui a la propriété remarquable de ne dépendre que de la géométrie locale du graphe. Nous expliquerons les conséquences de ce résultat pour le modèle des forêts couvrantes, en particulier la preuve d'une transition de phase d'ordre 2 avec le modèle des arbre couvrants critiques sur les graphes isoradiaux, introduit par Kenyon. Finalement, nous considérons la courbe spectrale de ce Laplacien massique et montrons qu'il s'agit d'une courbe de Harnack de genre 1. Il s'agit d'un travail en collaboration avec Cédric Boutillier et Kilian Raschel.

Inspiré par le modèle d’Ewens, nous proposons une distribution non-uniforme sur les permutations, où chaque permutation à un poids qui dépend de son nombre de records (i.e. maximums de gauche à droite). Nous étudions comment ce biais influence d’autre statistiques classiques, puis nous analysons la complexité moyenne de quelques algorithmes simples. Nous proposons également un algorithme linéaire de génération aléatoire pour cette distribution.
C’est un travail effectué en collaboration avec Mathilde Bouvel, Cyril Nicaud et Carine Pivoteau.

Si m>0 est un entier, les chemins de m-Dyck sont une variante des chemins de Dyck dont les pas sont +1 et -m, en bijection avec les arbres (m+1)-aires. Je présenterai une nouvelle bijection reliant deux familles de tels chemins (les préfixes de chemins de m-Dyck et les chemins de m-Łukasiewicz). Je montrerai comment utiliser cette bijection pour construire un algorithme de génération aléatoire très efficace (linéaire en temps et consommant un nombre de bits aléatoire quasiment égal à l'entropie des chemins).

We consider the large scaling limit of domino tilings known as pyramid partitions, introduced by Kenyon and Szendroi, using techniques developed in the mathematical physics community to deal with Schur processes. We give a flavor of the different limiting processes. If time permits, we consider variations and generalizations such as Pfaffian processes and strict plane partitions, skew pyramid partitions, and other models.

Un sous-problème du problème ouvert consistant à exhiber une bijection explicite entre matrices à signes alternants et partitions planes totalement symétriques auto-complémentaires consiste à trouver une bijection explicite entre ce que l'on appelle (n, k) trapézoïdes Gog et (n, k) trapézoïdes Magog. Une bijection relativement intriquée a été proposée par Biane et Cheballah dans le cas où k = 2. Nous présenterons une bijection beaucoup plus élémentaire pour ce même cas.

Les chemins du plan confinés dans un quadrant --plus généralement, dans un cône convexe-- ont été beaucoup étudiés ces dernières années, et ont donné lieu à de jolis résultats. Le plus remarquable dit que, pour les chemins à petits pas, la série génératrice est différentiellement finie si et seulement si un certain groupe de transformations rationnelles, construit à partir des pas autorisés, est fini. Les méthodes employées, allant de l'algèbre élémentaire sur les séries formelles à l'analyse complexe, en passant, entre autres, par le calcul formel, sont variées, ce qui participe au charme du sujet.
Mais quid des chemins dans un cône non convexe, et, typiquement, des chemins évitant un quadrant ? On étudiera les deux cas les plus naturels (pas NSEO, quadrant négatif ou quadrant Ouest interdit), en esquissant avec optimisme ce que pourrait être une classification pour ce problème.

Une configuration du modèle à 8 sommets est une orientation des arêtes de Z^2 qui vérifient qu'en tout sommet de Z^2 il y a 0, 2 ou 4 arêtes entrantes. Nous munissons l'ensemble de ces configurations d'une loi L définie à partir de 4 paramètres (a,b,c,d) qui sont des poids locaux. L'objectif de cet exposé est d'étudier la corrélation qui existe entre les orientations de 2 arêtes distantes dans une configuration distribuée suivant la loi L. Nous verrons que, si a+c=b+d (qui sont des conditions d'intégrabilité de notre modèle comme diraient les physiciens), on peut calculer la valeur exacte de ces corrélations généralisant ainsi des travaux de Kandel, Domany et Nienhuis de 1990. Pour cela, je présenterai un lien entre ce modèle avec a+c=b+d, un automate cellulaire probabiliste et un système de particules en interaction. Par la suite, leur étude se fera à l'aide d'outils probabilistes et issus de la combinatoire analytique.

As an introduction, I will shortly motivate the problem of representing de Bruijn graphs by presenting genome assembly, a fundamental task in bioinformatics. It consists in reconstructing the text of an unknown genome given only short fragments produced by a DNA sequencer. Most popular assembly algorithms use a de Bruijn graph, which is a graph over all substrings of length k present in the input, with edges consisting of all the exact suffix-prefix overlaps of length (k-1). It is crucial to have compact data structures in order to represent large graphs in memory. We have recently studied a model of succinct data structures for de Bruijn graphs, that we call navigational data structures [Chikhi et al, RECOMB 2014]. They support a useful but limited set of graph traversal operations; for instance, testing membership of nodes is not supported nor is it necessary. We prove theoretical space lower bounds to show the limitations of these types of approaches. The proofs rely on creating and counting families of graphs. We wonder whether our constructions could be improved, as there remains a gap between these lower bounds and the best known upper bounds.

Eppstein et Mumford (2014) ont récemment défini l'ensemble des polyèdres en coin comme l'ensemble des polyèdres 3D dont les sommets sont à coordonnées entières positives, les arêtes sont parallèles aux axes de coordonnées et tous les sommets sont visibles depuis l'infini dans la direction (1,1,1). Ils décrivent l'ensemble des graphes de polyèdres en coin, i.e. l'ensemble des graphes qui peuvent être squelette d'un polyèdre en coin : vus comme cartes planaires, il s'agit exactement des graphes duaux de certaines triangulations bicoloriées particulières, que nous appelons triangulations en coin enracinées. Nous comptons les graphes de polyèdres en coin en déterminant la série génératrice des triangulations en coin enracinées selon leur nombre de sommets : nous en obtenons une expression explicite en fonction de la série génératrice des nombres de Catalan. Nous montrons tout d'abord que ce résultat découle de la méthode classique de décomposition de Tutte. Ensuite, pour expliquer l'apparition des nombres de Catalan, nous donnons une décomposition algébrique directe des triangulations en coin~: en particulier nous mettons en évidence une famille de triangulations en amande qui admet une décomposition structurellement équivalente à celle des arbres binaires. Pour finir nous présentons rapidement une bijection directe entre les arbres binaires et ces triangulations en amande.

Dans le cadre de nos travaux sur les propriétés combinatoires des programmes concurrents, nous nous intéressons à un modèle très simplifié (d'un point de vue concurrence) à des classes de structures discrètes croissantes: les diamants croissants. Ces structures ont une série génératrice définie par une équation différentielle d'ordre 2 : F'' = G(F). Nous présenterons les asymptotiques du nombre d'objets de taille n pour différents modèles de diamants (planaires ou non, à arités contraintes, ...), ainsi que des bijections avec des objets connus tels que les graphes cacti croissants ou arbres unaires-binaires croissants.

Une partition d'un entier n est une suite décroissante d'entiers positifs (appelés parts) dont la somme est égale à n. Les identités de Rogers-Ramanujan établissent que pour tout n, le nombre de partitions de n telles que la différence entre deux parts consécutives est au moins 2 est égal au nombre de partitions de n en parts congrues à 1 ou 4 modulo 5. Plus généralement, les identités du type Rogers-Ramanujan établissent des égalités entre certains types de partitions avec des conditions de différence et des partitions avec des conditions de congruence. A partir des années 80, plusieurs identités de type Rogers-Ramanujan ont été découvertes à partir de la théorie des algèbres de Lie, mais la plupart d'entre elles ne sont pas encore comprises combinatoirement. Dans cet exposé, je présenterai une preuve combinatoire, un raffinement et une généralisation de l'une d'elles, l'identité de Siladic. La preuve utilise des équations aux q-différences et certaines idées de la méthode des mots pondérés introduite par Alladi et Gordon pour prouver combinatoirement et généraliser le théorème de Capparelli, une autre identité de partitions venue des algèbres de Lie.

Dans les cellules eucaryotes, à chaque mitose, les chromosomes sont raccourcis car la DNA-polymérase n’est pas capable de dupliquer une des extrémités du chromosome. Afin d’éviter la perte d’information génétique, qui pourrait être catastrophique pour la cellule, les chromosomes disposent de télomères à leurs terminaisons. Ces télomères ne contiennent aucune information génétique : ce sont des répétition de sequences T-T-A-G-G-G des milliers de fois. À chaque mitose, il y a donc un raccourcissement des télomères. Puisque leur longueur est finie, lorsque les télomères sont trop courts, la cellule ne peut plus se diviser : elle entre en sénescence réplicative. Notre modèle tente de reproduire les deux phases du raccourcissement télomèrique : la première, l’état initial de nos cellules, lorsque les télomères sont réparés par une protéine appelée télomérase; la seconde, où la télomèrase est inhibée, provoquant le grignotage progressif des télomères jusqu’à la sénescence.
Ce travail est fait en collaboration avec Zhou Xu et Thibault Bourgeron.

Soit v un chemin arbitraire constitué de pas Nord et Est. Le treillis Tam(v), basé sur tous les chemins faiblement au dessus de v avec les mêmes extrémités que v, a été introduit par Préville-Ratelle et Viennot (2014) et correspond au treillis de Tamari classique dans le cas v=(NE)^n. Ils ont démontré que Tam(v) est isomorphe au treillis dual de Tam(vv), où vv est v renversé avec N et E échangés. Notre contribution principale est une bijection entre les intervalles de Tam(v) et les cartes planaires non-séparables. Il s'ensuit que le nombre d'intervalles dans Tam(v) sur tous les chemins v de longueur n est donné par (2 (3n+3)!)/((n+2)! (2n+3)!). Cette formule a été obtenue par Tutte (1963) pour les cartes planaires non-séparables. Nous démontrons aussi que l'isomorphisme entre Tam(v) et le dual de Tam(vv) est équivalent à la dualité des cartes par notre bijection.
Travail joint avec Louis-François Préville-Ratelle.

Une transformation d'un espace est dite randomisante si son itération tend à uniformiser la distribution des configurations de cet espace. Plus précisément, quand on fixe la mesure de probabilité initiale non uniforme (la distribution initiale), l'itération de la transformation fait converger cette mesure vers la mesure uniforme. De tels comportements ont été remarqués expérimentalement dans certains automates cellulaires et sous-décalages de dimension 2. Dans cet exposé, je présenterai nos récentes avancées dans l'étude des causes et des limites de ces phénomènes, qui nous ont amené à la première preuve rigoureuse de leur existence. Cette preuve repose sur le fort contenu algébrique des systèmes considérés qui donne à leur évolution temporelle une structure géométrique autosimilaire. Dans un sous-décalage particulier (celui de Ledrappier), nous obtenons des changements surprenants de dynamique directionnelle suivant la direction considérée.

En 2001, Barcucci, Del Lungo, Pergola et Pinzani ont exprimé la fonction génératrice (suivant les inversions) des permutations évitant le motif 321, sous forme de quotient de q-analogues de fonctions de types Bessel. En me basant sur des travaux de Stembridge, Bousquet-Mélou et Viennot, autour des empilements de pièces et des empilements de segments, j'expliquerai comment retrouver ce résultat et le généraliser aux permutations affines. Ceci donnera l'occasion d'introduire la nouvelle famille des polyominos parallélogrammes "périodiques" et leurs connexions avec des empilements de segments bien particuliers que j’énumérerai. Cet exposé est basé sur des travaux en commun avec Riccardo Biagioli, Mireille Bousquet-Mélou et Philippe Nadeau.

Le PASEP (partially asymmetric exclusion proccess) est un model de mécanique statistique décrivant par une chaîne de markov, un système de particules en interaction sautant à gauche et à droite, sur un réseau unidimensionel de taille fixée. Les tableaux boisés sont des objets combinatoires en bijection avec les permutations, qui permettent de décrire l'état stationnaire du PASEP. Il est même possible de définir une chaîne de Markov sur les tableaux boisés qui se projette sur le PASEP. La projection envoie un tableau boisé sur l'état du PASEP correspondant à son bord sud-est, en particulier, les coins externes/internes du bord sud-est du tableaux boisé, correspondent aux sites où un changement d'état est possible.
Nous énumérerons les coins en mettant les coins externes en bijection avec les run de taille 1 dans les permutations. Nous en déduirons, à taille fixée, le nombre moyen de sauts de particules possibles dans un état du PASEP dans le cas alpha=beta=q=1. Enfin nous présenterons un raffinement conjectural de l'énumération des coins, qui généraliserait le résultat au cas q=1 et, alpha et beta quelconques.

Un arbre et/ou est un arbre dont les nœuds internes sont étiquetés soit par le connecteur logique ET, soit par le connecteur logique OU, et dont les feuilles sont étiquetées par des littéraux choisis parmi k variables booléennes {x_1,...,x_k} et leurs négations. Un tel arbre calcule une fonction booléenne à k variables, i.e. une fonction de {0,1}^k dans {0,1}.
Je m'intéresse dans cet exposé à décrire la fonction booléenne aléatoire calculée par un arbre et/ou aléatoire, en fonction des propriétés de l'arbre aléatoire choisi. Les résultats que je présente, obtenus en collaboration avec N. Broutin (Inria-Rocquencourt), concernent les arbres et/ou obtenus en étiquetant aléatoirement des arbres aléatoires standards : arbre de Catalan, arbre de Galton-Watson, arbre binaire de recherche aléatoire, etc.
Notre résultat principal décrit le comportement de la distribution induite sur l'ensemble des fonctions booléennes en fonction de la limite locale de l'arbre aléatoire sous-jacent.

Considérons un grand tableau de Young rectangulaire avec un rapport largeur/longueur fixé. Pittel et Romik (2007) ont montré que la surface aléatoire associée converge vers une limite déterministe. Nous étudions les fluctuations autour de cette limite. Nous montrons qu'en les coins, ces fluctuations sont gaussiennes alors que sur les bords, elles convergent vers la loi de Tracy-Widom.

Analytic combinatorics studies the asymptotic behavior of sequences through the analytic properties of their generating functions. In addition to the (now classical) univariate theory, recent work in the study of analytic combinatorics in several variables has shown how to derive asymptotics for the coefficients of certain D-finite functions by representing them as diagonals of multivariate rational functions. This talk examines the problem from the point of view of computer algebra: given a multivariate rational function G/H whose Taylor expansion in an open domain of convergence around the origin has all non-negative coefficients (known as the ‘combinatorial case’) we determine, under certain generic conditions, dominant asymptotics for the diagonal coefficient sequence in bit complexity singly exponential in the total degree of the denominator H. This provides, to our knowledge, the first complexity estimates for the theoretical work of Pemantle and Wilson, and their collaborators, on analytic combinatorics in several variables. Several applications to different areas of combinatorics will be discussed.

On étudie l'interface de compétition dans la percolation de dernier passage (LPP) introduite par Ferrari et Pimentel en 2005. Le mouvement de cette interface peut être couplé à celui d'une particule de deuxième classe dans le processus d'exclusion simple totalement asymétrique (TASEP). On démontrera que, dans les cas correspondants à des chocs en TASEP, le comportement de l'interface est gouverné par l'indépendance de deux temps de LPP. Travail avec Patrik Ferrari.

Most modern processors are heavily parallelized and use predictors to guess the outcome of conditional branches, in order to avoid costly stalls in their pipelines. We propose predictor-friendly versions of two classical algorithms: exponentiation by squaring and binary search in a sorted array. These variants result in less mispredictions on average, at the cost of an increased number of operations. These theoretical results are supported by experimentations that show that our algorithms perform significantly better than the standard ones, for primitive data types.

Un arbre croissant est un arbre étiqueté, tel que la suite des étiquettes de tout chemin de la racine à une feuille est strictement croissante. Ce modèle a été largement étudié dans différents contextes, notamment en théorie de la concurrence. Mais ce modèle n'est pas suffisamment expressif dans ce domaine. Nous allons l'étendre de la manière suivante : - la suite des étiquettes de tout chemin de la racine à une feuille est toujours strictement croissante - mais nous autorisons une étiquette a apparaître 2 fois dans l'arbre. La difficulté réside ici dans le fait que les différentes parties de l'arbre ne sont plus indépendantes, ce qui rend difficile l’application de la méthode symbolique pour spécifier ces classes. Nous présenterons ici une méthode pour le spécifier, ainsi qu'une extension à des modèles plus compliqués.