L'objectif de ce mini-cours est de présenter de la façon la plus élémentaire possible la convergence faible locale des graphes introduite par Benjamini et Schramm en 2001 et développée par Aldous et Steele (2004), Aldous et Lyons (2007). Nous montrerons comment cette notion peut être utilisée dans des dénombrements asymptotiques et dans des problèmes d'optimisation combinatoire.

Le but du mini-cours sera de faire un cours introductif à différentes méthodes énumeratives à travers l'exemple des pavages par dominos du diamant aztèque. On essaiera de voir les fonctions (super)-symétriques, les moments de polynômes bi-orthogonaux, les évaluations de determinants, les algorithmes de génération...

Aucun preacquis requis.

L'intégrabilité est une propriété des systèmes physiques avec un nombre suffisant de symétries, qui implique l'existence de lois de conservation, et permet souvent des solutions exactes et élégantes, avec des relations profondes à l'algèbre et la géométrie. Les problèmes posés peuvent se reformuler en termes purement combinatoires ou probabilistes, car liés à l'énumération pondérée de configurations explicites.

Dans ce cours, nous exposons essentiellement deux types de manifestation de l'intégrabilité en combinatoire : quantique et discrète.

La première séance est dédiée à l'intégrabilité quantique. Nous proposons d'abord un modèle simple, par le biais de l'énumération des triangulations Lorentziennes, qui possède une famille de matrices de transfert commutantes, et permet une énumération exacte. Ensuite, nous traitons l'exemple standard du modèle à six vertex sur le réseau carré, et son application à l'énumération des matrices à signe alternant et des partitions planes descendantes.

La seconde séance est dédiée à l'intégrabilité discrète. En partant de l'exemple des frises de Coxeter-Conway, nous reformulerons le problème en termes de connexions plates sur l'espace des solutions d'un système d'équations récurrentes, le T-système pour SL(2). En interprétant graphiquement ces connexions, nous reformulons le problème en termes de chemins non-intersectants sur un réseau, et finalement en termes de dimères sur un graphe. Nous proposons également une relation avec la structure d'algèbres amassées, une généralisation aux T-systèmes infinis, leur relation avec les matrices à signe alternant, et le phénomène de courbes arctiques en grande taille. Enfin, si le temps le permet, nous ferons une brève incursion dans le monde non-commutatif intégrable, qui permet de remplacer la génération de configurations par des polynômes en variables non-commutatives.

Over the last few years a wide array of random graph models have been postulated to understand properties of empirically observed networks. Most of these models come with a parameter $t$ (usually related to edge density) and a (model dependent) critical time $t_c$ which specifies when a giant component emerges. There is evidence to support that for a wide class of models, under moment conditions, the nature of this emergence is universal and looks like the classical Erdos-Rényi random graph, in that the extent of the range of the parameter in which phase transition occurs, but also of the sizes and structures of the large connected components within this range (when equipped with the graph distance) converge to random fractals related to Aldous's celebrated continuum random tree.

Our aim is to present and discuss a general program for proving such results. The results apply to a number of fundamental random graph models including the configuration model, inhomogeneous random graphs modulated via a finite kernel and bounded size rules. This is based on joint work with S. Bhamidi, S. Sen and X. Wang.

Nous considérons un modèle de couplage entre deux populations d’objets (par exemple hommes/femmes, familles/maisons ou patients/donneurs). Chaque population est divisée en plusieurs classes, et leurs compatibilités sont décrites par un graphe biparti. Les objets arrivent dans le système selon un processus en temps discret et partent après avoir été apparié.

Ce modèle, initialement proposé par Caldentey, Kaplan and Weiss (2009), peut être vu comme un cas très particulier de réseaux de files d’attente sans notion de serveur, où le service est remplacé par des appariements instantanés.

Nous étudions des différentes politiques d’appariements, et en particulier la question d’ergodicité de la chaîne de Markov décrivant l’évolution du système. Nous commençons par établir des conditions nécessaires sur le processus des arrivées, données par une variante du lemme de mariage dans le modèle classique.

Nous allons ensuite montrer l’existence d’une politique pour laquelle ces conditions sont également suffisantes. Cela n’est pas le cas de toutes les politiques d’appariement, un contre-exemple étant la politique des priorités.

A la fin de l’exposé, nous allons parler de variantes de ce modèle et de quelques questions ouvertes. Travail commun avec Ivo Adan, Varun Gupta, Jean Mairesse et Gideon Weiss.

La géométrie stochastique est l'étude d'objets issus de la géométrie euclidienne dont le comportement relève du hasard. Si les premiers problèmes de probabilités géométriques ont été posés sous la forme de casse-têtes mathématiques, le domaine s'est considérablement développé depuis une cinquantaine d'années de part ses multiples applications, notamment en sciences expérimentales, et aussi ses liens avec l'analyse d'algorithmes géométriques.

L'exposé sera centré sur la description des polytopes aléatoires qui sont construits comme enveloppes convexes d'un ensemble aléatoire de points. On s'intéressera plus particulièrement aux cas d'un nuage de points uniformes dans un corps convexe fixé ou d'un nuage de points gaussiens et on se focalisera sur l'étude asymptotique de grandeurs aléatoires associées, en particulier via des calculs de variances limites. Seront également évoqués d'autres modèles classiques de la géométrie aléatoire tels que la mosaïque de Poisson-Voronoi.

Un couplage parfait dans un graphe est un ensemble d'arêtes touchant chaque sommet exactement une fois. On s'intéresse au problème consistant à estimer le nombre de couplages parfaits dans les graphes réguliers (i.e. dont tous les sommets ont le même nombre de voisins), qui est un problème non trivial ayant des applications en physique statistique et en chimie moléculaire. Dans les graphes bipartis, trouver ce nombre de couplages parfaits revient à calculer le permanent d'une matrice doublement stochastique. Dans le cas général, c'est plus compliqué. Je monterai que sous des conditions naturelles garantissant l'existence d'au moins un couplage parfait, il y a en fait un nombre exponentiel de couplages parfaits. Cela résout une conjecture de Lovasz et Plummer formulée dans les années 70.
Il existe plusieurs autres problèmes très jolis sur les couplages parfaits qui sont toujours ouverts après 40-50 ans, j'essaierai d'en donner un bref aperçu.

Travail en commun avec F. Kardos, A. King, D. Kral, et S. Norine.

On se donne un collier ouvert formé de $ n$ perles. Chaque perle est d’un certain type parmi $ t$ types possibles. On suppose qu’il y a un nombre pair de perles de chaque type. Goldberg et West ont prouvé en 1984 qu’il était possible de couper le collier en $ t$ endroits et de partitionner les $ t+1$ sous-colliers obtenus en deux groupes contenant chacun autant de perles de chaque type, et ce indépendamment du nombre total $ n$ de perles. Si le collier est à partager entre deux personnes, on a ainsi obtenu un partage équitable du collier.

Ce résultat a depuis été généralisé de plusieurs manières (par exemple, pour un partage équitable entre plus de deux personnes) et pose un certain nombre de questions ouvertes (par exemple, peut-on calculer rapidement un tel partage ?). L’objectif de cet exposé est de présenter un certain nombre de ces généralisations et de ces questions ouvertes.

On étudie deux processus de branchement, limites d'échelle d'automates cellulaires, dans lesquels des particules positives (resp. négatives) se déplacent à vitesse 1 (resp -1) et donnent naissance à des particules de charge opposée selon des processus de Poisson. Quand deux particules se rencontrent, dans un premier modèle, elles s'annihilent, dans un second, l'une d'elle, choisie équiprobablement, est détruite et l'autre continue son chemin. On s'intéresse aux distributions stables de ces processus.

A planar map is outerplanar if all of its vertices belong to a single (outer)face. The scaling limit for various classes of large planar maps has been shown to be the so-called “Brownian Map”; under certain conditions, however, different asymptotic behaviours may emerge, and some classes of planar maps with a macroscopic face admit Aldous's CRT, or a scalar multiple thereof, as the scaling limit. We shall see that this is the case for outerplanar maps as well: using a bijection by Bonichon, Gavoille and Hanusse one can show that uniform outerplanar maps with $n$ vertices, suitably rescaled by a factor $1/\sqrt{n}$, converge to $7\sqrt{2}/9$ times the CRT.

Les nombres $p$-adiques partagent un certain nombre de similarités avec les nombres réels : ils s'obtiennent tous deux en complétant le corps $\mathbb{Q}$ des nombres rationnels pour une certaine distance, ils peuvent se représenter tous deux comme des suites infinies de chiffres et leur ensemble est, dans les deux cas, munis d'une mesure naturelle (la mesure de Haar).

De surcroît, de nombreux problèmes étudiés classiquement sur les réels ont un analogue $p$-adique qui s'avère parfois plus accessible. Ceci se produit notamment lorsque l'on s'intéresse aux matrices et aux polynômes aléatoires : « Comment se comporte le déterminant d'une matrice $p$-adique aléatoire ? », « Quel est le nombre moyen de racines d'un polynôme $p$-adique aléatoire ? », etc. Dans cet exposé, je présenterai quelques variations sur ce thème et m'attarderai plus longuement sur un résultat que j'ai obtenu récemment concernant le résultant des polynômes $p$-adiques aléatoires.

Travail en cours avec Philippe Biane. Si $G$ est un graphe dirigé, l'ensemble des arbres couvrants (dirigés) de $G$ est naturellement muni d'une structure de graphe : pour aller d'un arbre couvrant à l'un de ses voisins, on lui ajoute une arête sortant de sa racine, et on retire l'unique sortante du point d'arrivée. Nous montrons que le nombre d'arbres couvrants de ce (gros !) graphe se factorise de manière remarquable, comme un produit de facteurs comptant certaines forêts couvrantes du graphe de départ. Tout cela est fortement lié au «matrix-tree theorem», et à ses variantes probabilistes comme le «Markov chain tree theorem», que je rappellerai. La démonstration se base sur l'étude des sous-espaces invariants de la matrice laplacienne du gros graphe... et sur un peu de combinatoire !

One of the major bijective results in the area of enumeration of maps and in the area of studying uniform random maps is the approach initiated by Cori and Vauquelin and extended by Chapuy, Marcus and Shaeffer which treats rooted orientable maps of genus $g$. We extend their bijection for rooted maps drawn on any surface (orientable or non-orientable). It allows us to prove several results concerning asymptotic behavior of large maps on general surfaces as well as enumerative properties of them. This is a joint work with Guillaume Chapuy.

Dans une note datant du début des années 1950, John von Neumann a décrit un algorithme très simple, ne faisant intervenir que des comparaisons et des compteurs, pour simuler de manière exacte une variable aléatoire suivant la loi exponentielle ; algorithme qui a d'ailleurs été analysé en détail par Flajolet et Saheb dans les années 1980.

Von Neumann termine sa note par une indication intrigante, affirmant que la méthode peut facilement s'étendre à « toute distribution satisfaisant une équation différentielle du premier ordre ». À ma connaissance, cette extension n'a jamais été explicitée de manière satisfaisante.

Je présenterai une interprétation possible de la remarque de von Neumann, et un algorithme de simulation qui ressemble effectivement à une généralisation raisonnable de son algorithme. En l'occurrence, il s'agit de faire porter l'équation différentielle non pas sur la densité, mais sur la probabilité complémentaire de la fonction de répartition (« fonction de survie »).

Dans le parking de Page sur un intervalle discret, des voitures de taille 2 essaient de se garer uniformément jusqu'à ce qu'il ne reste plus que des places isolées.

Le but de cet exposé est de donner une preuve simple et probabiliste du fait (connu depuis longtemps) que la proportion du parking occupée par les voitures tend vers $ 1-e^{-2}$ lorsque la longueur du parking grandit. On discutera également d'autres conséquences de cette construction, et d'une généralisation à un parking infini.

Le groupe de tresses à $n$ brins est une extension du groupe symétrique à $n$ éléments. Dans un cas, les permutations peuvent s'obtenir à partir de transpositions élémentaires, consistant à échanger deux éléments voisins ; dans l'autre, les tresses sont obtenues à partir de générateurs d'Artin, consistant à échanger deux brins de tresses voisins, un brin passant au premier plan et l'autre à l'arrière-plan.

Le groupe de tresses appartient à la famille plus générale des groupes de Garside ; ceux-ci jouissent de propriétés combinatoires qui assurent entre autres l'existence de formes normales. Nous allons étudier l'évolution et la stabilisation de telles formes normales au cours de marches aléatoires dans le graphe de Cayley associé au groupe de tresses à $n$ brins.

Travail commun avec Jean Mairesse.

We study a generalized urn when s balls are drawn multiple drawing of two colors and random addition matrix according to a nonnegative random variable $X$. We discuss the limit in distribution of the normalized number of white balls in the opposite reinforcement model by estimating some dependence coefficients. Making a look for the self reinforcement rule by giving a generalization when the addition become random.

Travail commun avec Aguech Rafik et Selmi Olfa.

L'algorithme LLL est un algorithme de réduction de réseaux qui à partir d'une base d'un réseau, construit une "bonne base" ayant de bonnes propriétés euclidiennes (vecteurs courts et assez orthogonaux). L'algorithme LLL est omniprésent dans plusieurs domaines de l'informatique-mathématiques comme la cryptographie ou l'arithmétique des ordinateurs mais son comportement probabiliste est encore mal compris.

Une analyse probabiliste directe de LLL semble aujourd'hui encore difficile car sa dynamique en grande dimension est complexe. Ces dernières années, l'équipe de Caen a proposé plusieurs modèles simplifiés qui modélisent plus ou moins fidèlement les exécutions de LLL. L'équipe a également modélisé les réseaux euclidiens aléatoires rencontrés en cryptographie afin d'être le plus proche possible des applications.

L'objectif de l'exposé est de présenter les différents modèles d'exécution et de décrire les premiers résultats probabilistes obtenus. Nous discuterons de la cohérence des résultats avec ceux connus pour le LLL en petite dimension. Nous aborderons aussi la généralisation de ces résultats à des modèles plus complexes.

La présentation s'appuie sur les travaux de : Brigitte Vallée, Mariya Georgieva, Julien Clément, Fabien Laguillaumie, Antonio Vera, Manfed Madritsch, ...

Travail commun avec Samy Abbes (PPS, Univ. Paris 7).

Les monoides de trace et les empilements de pièces apparaissent dans différents contextes en combinatoire; ils constituent également des modèles naturels pour décrire les exécutions dans les systèmes asynchrones. La présence de commutations entre les pièces et l'absence d'une horloge globale rendent la probabilisation du modèle complexe. Dans ce travail, on introduit et on étudie la classe des mesures de probabilités dite de "Bernouilli" sur la frontière du monoide (les empilements infinis), parmi lesquelles la mesure "uniforme". Il s'agit des mesures de probabilités les plus simples adaptées au contexte. Pour les décrire, on s'appuie sur la théorie combinatoire des traces avec le polynôme de Möbius dans le rôle clé. On explicite le lien étroit entre cette mesure "uniforme" et deux objets classiques : la mesure de Parry de la dynamique symbolique et la mesure de Patterson-Sullivan de la théorie géométrique des groupes. Enfin, grâce aux résultats obtenus, on propose un algorithme de pseudo génération aléatoire uniforme des traces.

Je présenterai un automate cellulaire probabiliste (ACP) dont la définition est extrêmement simple, et qui intervient à la fois dans un problème de combinatoire (énumération des animaux dirigés) et dans la résolution d'un jeu lié à la percolation. Il est également lié au modèle des sphères dures en physique statistique. Dans un travail en collaboration avec James Martin, nous prouvons l'ergodicité de cet ACP pour toute valeur du paramètre de définition, répondant ainsi à des questions dans ces différents domaines.

Les arbres-B sont des arbres de recherche dans lesquels toutes les feuilles sont au même niveau. Dans un arbre-B de paramètre $ m$, les noeuds contiennent entre $ m$ et $ 2m$ clefs. Les différents noeuds de la frange de l'arbre évoluent comme une urne de Pólya. La transition de phase habituelle dans ces urnes, entre un comportement asymptotique gaussien ou non gaussien, se produit pour $ m=59$. Comme les valeurs de $ m$ courantes en pratique sont de plusieurs centaines, les arbres-B constituent un exemple concret de grande urne de Pólya. Pour $ m\geq 60$, après renormalisation, les fluctuations convergent fortement vers une variable aléatoire $ W$, dont nous obtenons quelques propriétés, bien que sa loi ne semble pas classique : c'est une densité dont le support est le plan complexe, elle possède des moments exponentiels, elle est solution d'une équation en loi de type ``smoothing equation''.

Travail commun avec Brigitte Chauvin, Daniele Gardy et Dai-Hai Ton-That.

Les cartes uniformes infinies du demi-plan ont été introduites par Angel comme limites locales de triangulations ou quadrangulations planaires uniformes. Le but de cet exposé est d’étudier l'universalité des modèles de percolation sur ces cartes. On calculera d’abord le seuil de percolation par site dans le cas quadrangulaire, puis on généralisera un résultat dû à Angel sur la limite d’échelle des probabilités de croisement, qui constitue un analogue naturel de la formule de Cardy dans les réseaux réguliers. Plus précisément, on montrera que cette quantité ne dépend pas du modèle de percolation ni du degré des faces de la carte, vérifiant dans ce cadre la conjecture d’universalité de Cardy.

La méthode symbolique permet de produire des spécifications, ainsi que des équations sur les séries génératrices associées aux classes combinatoires. Nous nous intéressons ici à décrire l'inverse des opérateurs de Polya (Mset, Cycle,...). En particulier, le multiset fait partie des opérateurs où trouver un sens combinatoire de l'inverse est possible, puisqu'il s'agit d'une forme de factorisation.

Dans cet exposé, nous montrons que l'opérateur multiset inverse est lié à la transformation d'Euler inverse et admet une forme close pour l'expression de sa série génératrice. Nous donnons aussi une interprétation combinatoire en terme de factorisation. Nous montrons ces résultats sur des exemples.

Strurmian words play an important role in combinatorics of words since they are exactly the words that have $n+1$ factors of length $n$. On the other hand, the recurrence function precisely describes the occurrence of factors inside a word. That is why the study of the recurrence function on strurmian words is so important.

Sturmian words are closely related to Kronecker sequences, defined as $k \mapsto \{k \alpha\} $ (where $\{\cdot \}$ is the fractional part), and thus to the Gauss dynamical system and continued fraction expansion; and the recurrence function itself is expressed with continuants.

We perform a probabilistic study of the recurrence function of strurmian words, and study the expectation and the distribution of the recurrence function. We use both tools of analytic combinatorics and dynamical systems, and follow the methods proposed by Cesaratto and Vallée in the study of other parameters of the Kronecker sequences.

(Joint work in progress with Valérie Bethé, Eda Cesaratto, Brigitte Vallée, Alfredo Viola)

Le package NewtonGF offre plusieurs outils de calcul efficace sur les séries génératrices des classes combinatoires décomposables. Il fournit notamment un oracle numérique, nécessaire au fonctionnement des générateurs de Boltzmann, ainsi que l'évaluation de leur paramètre. Nous ferons une démonstration de ses fonctionnalités.

Package développé en Maple, en collaboration avec Bruno Salvy.

We present Clones, a Matlab toolbox for exact sampling from the stationary distribution of a closed queueing network with finite capacities. This toolbox is based on recent results using a compact representation of sets of states that enables exact sampling from the stationary distribution without considering all initial conditions in the coupling from the past (CFTP) scheme. This representation reduces the complexity of the one-step transition in the CFTP algorithm to O(KM2), where K is the number of queues and M the total number of customers; while the cardinality of the state space is exponential in the number of queues. We focus on the algorithmic and implementation issues. We propose a new representation, that leads to onestep transition complexity of the CFTP algorithm that is in O(KM). We provide a detailed description of our matrix based implementation.