Journées de combinatoire de Bordeaux
11-13 février 2019, LaBRI, Bordeaux

On s'intéressera au comportement asymptotique d'objets discrets aléatoires (comme des marches aléatoires et des arbres aléatoires) lorsque leur taille tend vers l'infini, et on se demandera s’il existe une limite continue. Le cas échéant, on verra que son existence permet d'obtenir d'intéressantes conséquences à la fois dans le monde discret et dans le monde continu. Enfin, on étudiera plus spécifiquement le modèle des factorisations aléatoires minimales du $n$-cycle en transpositions (c'est-à-dire des factorisations du cycle $(1,\ldots,n)$ en produit de $n-1$ transpositions), qui fait l'objet d’un travail avec Valentin Féray.

The dimer model is a model from statistical mechanics corresponding to random perfect matchings on graphs. Circle patterns are a class of embeddings of planar graphs such that every face admits a circumcircle. In this talk I describe a correspondence between dimer models on planar bipartite graphs and circle pattern embeddings of these graphs. As special cases of this correspondence we recover the Tutte embeddings (a.k.a. harmonic embeddings) for resistor networks and the s-embeddings for Ising models. This correspondence is also the key for studying Miquel dynamics, a discrete integrable system on circle patterns.

This is joint work with Richard Kenyon (Brown University), Wai Yeung Lam (Brown University) and Marianna Russkikh (University of Geneva).

I will present an analytic study of the eigenvalues spectral distribution of some polynomials in independent random matrices in the limit of the large dimension. If the random matrices are unitary invariant matrices, the theory of non-commutative probability gves much information about the spectrum thanks to Voiculescu’s notion of freeness (related to non-crossing partitions). Here we only assume that the matrices are invariant by conjugation by permutation matrices. A more general approach is required, which so far was only providing a combinatorial description of the spectrum, thanks to the notion of traffic independence. Recently we observed that traffic independence implies freeness in an operator-valued sense, allowing to use techniques of free probability theory.

Nous considérerons un modèle de marche prudente en auto-interaction. Les trajectoires autorisées dans le plan sont auto-évitantes et satisfont une contrainte additionnelle (dite de prudence) : elles ne peuvent pas faire de pas en direction d’un site qu'elles ont déjà visité. En taille finie, la mesure uniforme sur ces trajectoires prudentes est perturbée par un Hamiltonien qui compte les auto-contacts. On prouvera qu'une transition d'effondrement intervient entre une phase dite étendue et une phase dite effondrée dans laquelle l'énergie libre croit linéairement avec le paramètre de couplage.

Pour les graphes finis, les configurations récurrentes du modèle du tas de sable sont en bijection avec les arbres couvrants, via un critère algorithmique de Dhar. De plus la distribution du nombre de grains sur ces configurations est, à une constante près, celle de l'activité externe au sens de Tutte. On s'intéresse à des extensions de ces propriétés dans le cas du graphe infini qu'est la grille Z^2 et pour des configurations bipériodiques. On étudie la récurrence en plaçant le puits du critère de Dhar à l'infini dans une direction de pente rationnelle. Les analogues des arbres couvrants sont alors les forêts couvrantes enracinées sur des cycles non-contractiles du tore décrivant la période. On montre bijectivement que la distribution de l'analogue de l'activité externe au sens de Tutte de ces forêts est invariante par rotation de la direction du puits.

Il s'agit d’un travail en commun avec Yvan Le Borgne.

Les permutations qui évitent des motifs ont été définies à la fin des années 60, et leur étude s'est développée à partir des années 90, surtout du point de vue énumératif. Mais ces quelques dernières années, les permutations évitant des motifs ont aussi été étudiées d’un point de vue probabiliste. Plus spécifiquement, cette ligne de recherche se concentre sur la description d'une permutation typique de grande taille prise dans une telle famille à motifs interdits. Cela s'entend de plusieurs manières : comportement limite de certaines statistiques (ou paramètres) de cette permutation aléatoire, limite d'échelle (en termes de permutons), ou encore plus récemment limites locale ou semi-locale. Cet exposé présentera un panorama de résultats récents obtenus sur le sujet, principalement sur les limites d'échelle de certaines classes de permutations. Un outil essentiel est la décomposition par substitution des permutations, qui permet de les représenter par certaines familles d'arbres. Les méthodes de la combinatoire analytique et la théorie des arbres aléatoires ne font alors pas tout le travail, mais fournissent une base solide sur laquelle s'appuyer.

Une fonction $f(x)$ est dite $l$-mahlerienne ($l >1$ entier) si elle vérifie une équation fonctionnelle de la forme

$a_0(x)f(x) + a_1(x) f(x^l) + a_2(x) f(x^{l^2}) +...+ a_n(x) f(x^{l^n}) = 0$

pour certains polynômes $a_0(x),...,a_n(x)$ non tous nuls. Ces fonctions apparaissent naturellement dans la théorie des automates : les séries génératrices des suites $l$-automatiques sont $l$-mahleriennes. Dans cet exposé, nous nous intéresserons aux fonctions $l$-mahleriennes a priori les plus simples, à savoir celles vérifiant une équation fonctionnelle de la forme $f(x) =p(x)f(x^l)$, où $p(x)$ est un polynôme à coefficients entiers. Nous montrerons comment certaines caractéristiques de $f(x)$ se reflètent sur $p(x)$, notamment en liaison avec la théorie des automates. Si le temps le permet, nous présenterons quelques analogies avec la théorie arithmétique des équations différentielles. Il s'agit d’un travail en commun avec S. Checcoli.

L'énumération de marches dans des cônes du plan a de nombreuses applications en combinatoire et en probabilités. Ces objets peuvent être traités par des techniques variées : combinatoires, analyse complexe, théorie des probabilités, calcul formel. Les marches restreintes au quart de plan ont beaucoup été étudiées mais le cas des marches restreintes aux trois quarts de plan est plus récent. Dans cet exposé, nous appliquons la méthode analytique pour les marches dans le quart de plan aux marches dans les trois quarts de plan. Cette méthode est composée de trois grandes étapes : écrire une équation fonctionnelle vérifiée par la série génératrice des excursions, la transformer en un problème frontière et le résoudre. Le résultat est sous la forme d'une intégrale sur un contour.

We look at properties of graphs that can be expressed in first order (FO) logic. Given such a property $A$ and a class $G$ of random graphs, we are interested in the limiting probability that a graph in $G$ satisfies $A$, when the number of vertices goes to infinity. First we survey what is known for the classical model $G(n,p)$, including zero-one laws and the celebrated theorem of Shelah and Spencer. Then we move to classes of graphs defined by a global condition, such as being acyclic or planar, under the uniform distribution. We survey recent results on zero-one laws, convergence laws, and non-convergence phenomena, both in FO and in the stronger monadic second order (MSO) logic. In particular, for graphs embeddable in a fixed surface other than the sphere, there is a striking difference between the results in FO and MSO logic.

Dans cet exposé, nous étudierons deux théories logiques du premier ordre sur les permutations. La première considère les permutations comme des bijections et est adaptée à décrire les cycles de la permutation, la seconde plutôt comme un mot ou comme des points dans une grille carrée (matrice de permutation) et permet de décrire les motifs de la permutation. Nous verrons que l'ensemble des propriétés qui peuvent se décrire dans les deux logiques est relativement restreint. Cela formalise en quelque sorte l'intuition que regarder une permutation comme un ensemble de cycles ou comme un mot sont deux points de vue orthogonaux. Nous finirons par une conjecture sur l'existence d'une loi de convergence pour une permutation uniforme aléatoire.

We introduce a new family of maps, namely tree-decorated maps where the tree is not necessarily spanning. To study this class of maps, we define a bijection which allows us to deduce combinatorial results, recovering as a corollary some results about spanning-tree decorated maps, and to understand local limits. Finally, we discuss the possible metric scaling limit of this map: the shocked map. We give certain properties and give the conjectured continuum construction. This is a work in progress with Avelio Sepúlveda.

On présente un nouvel ordre partiel sur les chemins de Dyck, motivé en partie par la structure cellulaire des diagonales des associaèdres. Cet ordre a quelques propriétés remarquables et en particulier il existe une formule close pour les nombres d'intervalles. On décrira aussi comment apparaît dans ce contexte une connexion inattendue avec des polytopes introduits par Saneblidze en topologie algébrique.

Pólya urns are urns where at each unit of time a ball is drawn uniformly at random and is replaced by some other balls according to its colour. We introduce a more general model, in which the replacement rule also depends on the value of the time modulo $p$.

Our key tool are generating functions, which encode all possible urn compositions after a certain number of steps. The evolution of the urn is translated into a system of differential equations and we prove that the moment generating functions are D-finite. From these we derive asymptotic forms of the moments. When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions.

Furthermore, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: we prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions. This is joint work with Cyril Banderier and Philippe Marchal.

We consider random rooted maps without regard to their genus. We address the problem of limiting distributions for six different parameters: vertices, leaves, loops, root edges, root isthmic constructions, root vertex degree. Each parameter has a different limiting distribution, varying from (discrete) geometric and Poisson to (continuous) Beta, normal, uniform, and an unusual bounded distribution characterised by its moments.

This is a joint work with Olivier Bodini, Julien Courtiel, and Hsien-Kuei Hwang.

Pour un nombre réel $\alpha$ donné, plaçons les points $ 0, \alpha, 2\alpha, \ldots , N \alpha$ sur le cercle unité. Ces points divisent le cercle unité en intervalles ayant au plus trois longueurs, l'une étant la somme des deux autres. Il s'agit du théorème des trois distances. Nous considérons ici deux versions bidimensionnelles duales de cet énoncé. Nous verrons que le prix à payer pour avoir un petit nombre de longueurs est que les formes associées ne sont pas des carrés mais sont de nature fractale : elles sont engendrées par une version symbolique de l'algorithme de fractions continues multidimensionnel de Brun.

Il s’agit d’un travail en collaboration avec P. Arnoux, D. H. Kim, W. Steiner et J. Thuswaldner.