On donnera une introduction aux cartes combinatoires sur des surfaces orientables. On espère qu'à la fin tout le monde sera capable de dessiner une carte de genre 2 sans trop prendre peur, et c'est là le premier objectif du cours. Le second objectif sera de tester sa compréhension des objets par la résolution de quelques problèmes de comptage simples, sur les cartes à une face notamment. Le troisième objectif sera de présenter succinctement le lien avec l'algèbre du groupe symétrique, et à quoi cela peut bien servir. Avoir au moins deux couleurs ou épaisseurs de stylo pourra aider à suivre.

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.

Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.

Le processus de contact peut être vu comme un modèle de propagation d'une épidémie en temps continu. Nous présenterons une construction graphique qui permet de faire le lien avec des modèles de percolation, et nous étudierons quelques propriétés de ce modèle: possibilité de survie, lois stationnaires, temps d'extinction...

Nous proposons deux versions équivalentes de l'hypothèse de Riemann. La première est relative à la probabilité que deux variables indépendantes suivant une même loi géométrique soient premières entre elles. La deuxième concerne l'asymptotique du nombre de lignes polygonales convexes croissantes à sommets entiers reliant l'origine au point de coordonnées (n,n).
(Les résultats ont été obtenus en collaboration avec Julien Bureaux.)

Dans le cadre de cet exposé, nous nous intéressons a des aspects quantitatifs de la théorie de la Concurrence, celle-ci étant formalisée dès les années 80 par Millner et Hoare. Nous manipulons deux types d'objets :
Les objets syntaxiques représentent des programmes parallèles, et les objets sémantiques en décrivent l’ensemble des traces d'exécution. Nous considérons ces objets au sein de classes combinatoires, et nous les étudions d'un point de vue quantitatif avec des outils de Combinatoire Analytique.

Il est bien connu que le passage de la syntaxe à la sémantique engendre une explosion combinatoire. Un parallèle avec la théorie des ordres partiels nous apporte une première information, plutôt restrictive : étant donné un programme, calculer le nombre de ses traces est un problème #P-complet (Brightwell & Winkler 1991).
Ainsi, nous avons deux objectifs majeurs : quantifier cette explosion en moyenne, pour des sous-classes intéressantes (pour la Concurrence) et générer, en pratique, uniformément des traces, le programme (syntaxique) étant fixé. Pendant l'exposé, nous passerons en revue les trois opérateurs fondamentaux auxquels nous nous sommes intéressés, en mettant en avant les challenges combinatoires que nous avons résolus (ou qu'il reste à réussir) afin d'obtenir les résultats quantitatifs escomptés et les outils de génération aléatoire adéquats.

Le model checking pour la vérification d'un système informatique est une technique basée sur la construction d'un modèle mathématique du système, le plus souvent un graphe, et la formalisation à l'aide d'une logique des propriétés qu'il doit vérifier. Une démarche algorithmique permet par une exploration exhaustive du graphe la validation du système, ou produit un exemple d'exécution qui l'invalide. Les domaines d'application se sont diversifiés au cours du temps grâce au développement de techniques et d'outils spécialisés sur des modèles plus expressifs, par exemple, temporisés ou probabilistes. Le model checking probabiliste permet d'obtenir des réponses quantitatives, on peut par exemple valider un système avec une probabilité >0,95.
Nous donnerons un apercu des méthodes utilisées, des résultats et les compromis nécessaires dus à l'explosion combinatoire inhérente. Nous présenterons ensuite la problématique particulière de l'analyse des événements rares et des résultats permettant dans certains cas d'y parvenir.

We analyze random labelled cubic planar graphs according to the uniform distribution. This model was analyzed first by Bodirsky et al. in a paper from 2007. Here we revisit and extend their work. The motivation for this revision is twofold. First, some proofs where incomplete with respect to the singularity analysis and we provide full proofs. Secondly, we obtain new results that considerably strengthen those known before. For instance, we show that the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance, while formerly it was only known that it is linear with high probability.
This is based on a joint work with Marc Noy (UPC) and Clément Requilé (FU Berlin - BMS).

Dans une première partie, je présenterai différentes problématiques liées à des statistiques d’occurrences de mots dans des génomes et décortiquerai plus en détail la question de savoir comment détecter si un mot a une fréquence d’apparition significativement anormale dans une séquence. Dans une deuxième partie, je présenterai différentes extensions pour tenir compte du fait qu’un motif d’ADN fonctionnel n’est pas toujours un « mot », mais qu’il peut avoir une structure plus complexe qui nécessite le développement de nouvelles méthodes statistiques.

Au cours de cet exposé, nous nous intéresserons aux chemins de basket (chemins à pas dans l'ensemble {−2,−1,+1,+2}). Il s'avère que les chemins de basket allant de 0 à 0, visitant 1 et restant strictement positif entre leurs extrémités sont comptés par les nombres de Catalan. Nous donnerons une bijection explicite rendant compte de ce fait et étudierons les statistiques qu'elle fait correspondre. Dans un second temps, nous regarderons le lien entre les chemins de basket et une autre classe d'objets combinatoires, à savoir les arbres unaires-binaires croissants dont la permutation obtenue en lisant les étiquettes en largeur évite 213.
Ce travail est en commun avec Éric Fusy, Cécile Mailler et Lucas Randazzo.

Une des manières les plus naturelles de simuler une triangulation uniforme de la sphère à n faces est d'utiliser une méthode de Monte-Carlo : on démarre avec une triangulation quelconque puis, de manière répétée, on choisit une arête uniformément et on la "flippe", i.e. on l'efface et on la remplace par l'autre diagonale du quadrilatère qui se forme. On montrera que le temps de mélange de la chaîne de Markov obtenue est au moins en n^{5/4}.

Un ensemble de Kakeya classique est un sous-ensemble du plan balayé par une aiguille de longueur 1 qui fait un tour complet sur elle-même (autour d'un centre mobile). Au début au 20ème siècle, Besicovitch a démontré qu'il existait des ensembles de mesure arbitairement petite (bien qu'il soit facile de vérifier qu'il n'y en a aucun de mesure nulle). Des questions analogues se posent lorsque l'on remplace le corps des nombres réels par d'autres corps munis d'une valeur absolue et d'une mesure de Haar. Je donnerai, dans cet exposé, des résultats valables sur le corps des nombres p-adiques (voire plus généralement des corps ultramétriques complets). Précisément, dans ce mesure, je définirai une mesure naturelle sur l'ensemble des ensembles de Kakeya puis je montrerai que, pour cette mesure, un ensemble de Kakeya est presque surement de mesure nulle.

Une carte combinatoire est un graphe connexe tel qu'autour de chacun de ses sommets, les demi-arêtes incidentes sont ordonnées de manière cyclique. Cet exposé présente deux de nos travaux récents, remettant au goût du jour l'étude énumérative de ces objets. Premièrement, nous décrivons une bijection, entre cartes et diagrammes de cordes, dont les conséquences pourraient avoir des répercussions en physique théorique et théorie du lambda-calcul. Ensuite, nous étudions le comportement asymptotique de certains paramètres comme le nombre de sommets. Cela s'inscrit dans le cadre plus général de l'analyse des équations différentielles non linéaires (comme celles de Ricatti), pour lesquelles nous proposons une nouvelle approche lorsque la série génératrice est non analytique.
Ces résultats ont été découverts en collaboration avec Karen Yeats et Noam Zeilberger d'une part, et Olivier Bodini et Sergey Dovgal d'autre part.

Un méandre est une configuration de deux courbes planes dans la sphère. De manière équivalente, il s'agit d'une carte planaire dont le graphe sous jacent est la réunion disjointe de deux cycles eulériens (en particulier chaque sommet est de valence 4). Les méandres s'encodent simplement avec des permutations ou des parenthésages cependant leur analyse asymptotique résiste aux mathématiciens. Dans un travail en commun avec Elise Goujard, Peter Zograf et Anton Zorich nous démontrons l'asymptotique polynomiale des méandres dont le nombre de bigones (= faces à 2 arêtes) est prescrit.

Dans le cadre du test de programmes concurrents, on s'intéresse au tirage aléatoire et uniforme d’exécutions de ces programmes. L'idée est de tirer un grand nombre d'exécutions possibles et de vérifier que ces exécutions ne violent pas la spécification du programme donné. Pour résoudre ce problème, nous cherchons des classes de programmes dont la combinatoire nous permet de construire des algorithmes efficaces. Dans cette présentation on proposera un algorithme de génération aléatoire uniforme d'exécutions de programmes séries-parallèles. On montrera que cet algorithme est entropique: qu'il utilise un nombre optimal de bits aléatoires. Ce résultat se base sur l'introduction de plusieurs algorithmes "élémentaires" pouvant être réutilisés dans d'autres contextes.

La question de la simulation exacte de lois de probabilités sur les réels est généralement étudiée sous un modèle « arithmétique » où on calcule de manière exacte sur des réels. Dans cet exposé, on se place au niveau « bit à bit », et on se demande ce qui peut être simulé exactement si on n'a qu'une mémoire finie.
On est alors naturellement amené à considérer des automates qui tirent à pile ou face et qui écrivent des mots, qu'on espère infinis, et qu'on interprète comme le développement de réels ; la question est donc de savoir quelles distributions sont simulables de la sorte. Le modèle est essentiellement celui considéré par Knuth et Yao en 1976, et pour lequel ils ont montré un résultat intrigant : si une loi simulable a une densité qui est une fonction analytique, alors cette densité est en fait polynomiale - ce qui exclut de fait de nombreuses lois usuelles.
Je présenterai un résultat plus nouveau de classification : étant donné un automate, on peut dire s'il simule une loi à atomes, ou à densité, ou une loi plus « méchante ». Je montrerai aussi des exemples qui interdisent une généralisation trop forte du résultat de Knuth et Yao.

Les chemins tandem sont des chemins dans le plan utilisant l'ensemble de pas {N,O,SE}, et plus généralement on peut considérer que l'on autorise tout pas de la forme (-i,j) en plus du pas SE. Kenyon, Miller, Sheffield, et Wilson ont récemment montré que les chemins tandem généraux sont en bijection avec les orientations bipolaires (avec un certain marquage).
Nous montrerons comment cette bijection peut être exploitée pour permettre de compter les chemins tandem généraux dans le quart de plan, ainsi que les orientations bipolaires associées.
Travaux en commun avec Mireille Bousquet-Mélou et Kilian Raschel

Partially commutative monoids provide a powerful tool to study graphs, viewing walks as words whose letters, the edges of the graph, obey a specic commutation rule. A particular class of traces emerges from this framework, the hikes, whose alphabet is the set of simple cycles on the graph. We show that hikes characterize undirected graphs uniquely, up to isomorphism, and satisfy remarkable algebraic properties such as the existence and uniqueness of a prime factorization. Because of this, the set of hikes partially ordered by divisibility hosts a plethora of relations in direct correspondence with those found in number theory. Further applications of these results will be presented, including several exact formulas for counting simple cycles. These offer a novel perspective on the problem of enumerating self-avoiding polygons on regular lattices.

Cet exposé vise quelques propriétés de contrôlabilité (approchée, nulle) des réseaux complexes gouvernés par une classe de processus Markoviens linéaires de décision. La dynamique est donnée par un couple consistant en un mode Markovien et un processus linéaire de décision à bruit multiplicatif régi par des coefficients dépendant du mode. Des métriques de contrôlabilité sont obtenues à l'aide de schémas stochastiques rétrogrades de type Riccati pour lesquels on indiquera la consistance. Ces résultats théoriques sont illustrés en relation avec l'intervention minimale visant à garantir un comportement lytique d'un modèle du virus lambda.

Une configuration d'un polynôme P est l'image réciproque de R U iR par le polynôme P. Elle est formée d'un ensemble de courbes plongées dans le plan complexe. Dans le cas particulier des polynômes unitaires à racines simples apparaît une notion naturelle d'équivalence entre les configurations, que l'on peut exprimer en des termes combinatoires. Cela nous permet alors de dénombrer les configurations des polynômes, aussi bien de manière exacte que de manière asymptotique.

Les nombres de Narayana comptent les chemins de Dyck en fonction de leur nombre de pics. Ces nombres présentent une propriété intéressante de symétrie. On généralisera tout d'abord ce résultat aux paires de chemins de Dyck qui ne se croisent pas, puis on donnera un contre-exemple à une tentative de généralisation à un plus grand nombre de chemins.
En utilisant des idées très similaires à celles utilisées dans la preuve du cas de la paire de chemin, impliquant une construction de Bonichon sur les forêts de Schnyder, on obtiendra ensuite des résultats intéressants sur les marches du plan. On notera que ces derniers résultats sont utiles dans la résolutions d'un problème énoncé par Bousquet-Mélou et Mishna en 2010, et d'un autre formulé par Burrill, Courtiel, Fusy, Melczer et Mishna en 2015.
Travail en collaboration avec Julien Courtiel, Éric Fusy, et Marni Mishna.

I will talk about generalized p-angulations in dimension higher than 2, which are gluings of elementary building blocks with p external faces. In two dimensions, p-angulations which maximize the number of vertices at fixed number of p-gons are the planar ones. They belong to the same universality class in the sense that their generating functions exhibit the same critical behavior. The situation in higher dimension appears to be richer. I'll present counting results and the critical behaviors of a number of such models.

Une urne de Pólya est un processus stochastique décrivant la composition d'une urne contenant des boules de différentes couleurs. L'ensemble des couleurs est usuellement un ensemble fini {1, ..., d}. A chaque instant n, une boule est tirée uniformément au hasard dans l'urne (notons c sa couleur), remise dans l'urne accompagnée de R(c,i) boules de couleur i pour toute couleur i.
Je présente dans cet exposé une généralisation de ce modèle à un ensemble infini, et même potentiellement indénombrable de couleurs. Dans ce nouveau modèle, la composition de l'urne est une mesure (potentiellement non-atomique) sur un espace Polonais.
Ceci est un travail en collaboration avec Jean-François Marckert.

The number of planar Eulerian maps with n edges is well-known to have a simple expression. But what is the number of planar Eulerian orientations with n edges? This problem appears to be difficult. To approach it, we define and count families of subsets and supersets of planar Eulerian orientations, indexed by an integer k, that converge to the set of all planar Eulerian orientations as k increases. The generating functions of our subsets can be characterized by systems of polynomial equations, and are thus algebraic. The generating functions of our supersets are characterized by polynomial systems involving divided differences, as often occurs in map enumeration. We prove that these series are algebraic as well. We obtain in this way lower and upper bounds on the growth rate of planar Eulerian orientations, which appears to be around 12.5.

Dans cet exposé, nous expliquerons comment énumérer la famille des graphes planaires 4-réguliers, en exhibant leur série génératrice. Cette dernière est obtenue en utilisant une large variété d'outils, tant au niveau des graphes que de celui des cartes planaires. En sous-produit de cette méthode, nous obtenons un système d'équations permettant l'énumération des cartes planaires 3-connexes et 4-régulières, que nous présenterons aussi.
Ce travail est en collaboration avec Marc Noy et Juanjo Rué (UPC, Barcelona).

Les tableaux de permutations et tableaux EW sont des remplissages de diagrammes de Young avec des 0 et des 1, chacun défini en termes de motifs exclus. Il est connu que le nombre de tableaux de permutations et de tableaux EW d'un diagramme de Young fixé est le même, mais jusqu'à présent il n'existe aucune bijection entre ces deux types de tableaux. Nous présentons une telle bijection, et étudions certaines de ses propriétés, notamment concernant certaines statistiques des tableaux. La bijection en question passe par certaines permutations liées aux deux types de tableaux. Travail en commun avec Einar Steingrimsson et Jason Smith.