Journées de combinatoire de Bordeaux 2019 (JCB 2019)

← Retour à la page principale

Les JCB 2019 ont eu lieu du lundi 11 au mercredi 13 février 2019. Les exposés ont eu lieu dans l’amphithéâtre du LaBRI (Bâtiment A30) à l’Université de Bordeaux.

Orateurs et résumés

Accéder au programme complet au format pdf.

• Igor Kortchemski (CNRS & École polytechnique) Comportement asymptotique de grandes structures discrètes aléatoires
  Résumé

  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 -cycle en transpositions (c’est-à-dire des factorisations du cycle en produit de transpositions), qui fait l’objet d’un travail avec Valentin Féray.
• Sanjay Ramassamy (DMA, ENS Paris) Dimers and circle patterns
  Résumé

  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).

• Camille Male (IMB, Bordeaux) Asymptotic freeness over the diagonal of random matrices
  Résumé

  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.
• Nicolas Pétrélis (Laboratoire Jean Leray, Nantes) Transition d’effondrement de la marche prudente en deux dimensions
  Résumé

  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.
• Henri Derycke (LaBRI, Bordeaux) Une notion de récurrence dans le modèle du tas de sable sur le réseau carré
  Résumé

  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 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.

• Mathilde Bouvel (Université de Zurich) Formes limites de permutations évitant des motifs
  Résumé

  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.
• Julien Roques (Institut Camille Jordan, Lyon) À propos de certaines propriétés arithmétiques des fonctions de Mahler
  Résumé

  Une fonction est dite -mahlerienne ( entier) si elle vérifie une équation fonctionnelle de la forme

  pour certains polynômes non tous nuls. Ces fonctions apparaissent naturellement dans la théorie des automates : les séries génératrices des suites -automatiques sont -mahleriennes. Dans cet exposé, nous nous intéresserons aux fonctions -mahleriennes a priori les plus simples, à savoir celles vérifiant une équation fonctionnelle de la forme , où est un polynôme à coefficients entiers. Nous montrerons comment certaines caractéristiques de se reflètent sur , 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.

• Amélie Trotignon (Institut Denis Poisson, Tours) Marches dans trois quarts de plan
  Résumé

  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.
• Marc Noy (Universitat Politècnica de Catalunya) Logic and random graphs
  Résumé

  We look at properties of graphs that can be expressed in first order (FO) logic. Given such a property and a class of random graphs, we are interested in the limiting probability that a graph in satisfies , when the number of vertices goes to infinity. First we survey what is known for the classical model , 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.
• Valentin Féray (Université de Zurich) Logique(s) du premier ordre sur les permutations
  Résumé

  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.
• Luis Fredes (LaBRI, Bordeaux) Bijections for tree-decorated maps and applications to random maps
  Résumé

  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.
• Frédéric Chapoton (IRMA, Université de Strasbourg) Les demi-treillis dextres et les polytopes de Hochschild
  Résumé

  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.
• Michael Wallner (LaBRI, Bordeaux) Periodic Pólya Urns and Asymptotics of Young tableaux
  Résumé

  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 .

  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.

• Sergey Dovgal (LIPN et IRIF, Paris) Asymptotic distribution of parameters in random maps
  Résumé

  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.

• Valérie Berthé (IRIF, Paris) Versions multidimensionnelles du théorème des trois longueurs
  Résumé

  Pour un nombre réel donné, plaçons les points 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.

Emploi du temps

Lundi 11 février

Mardi 12 février

Mercredi 13 février

Participants

• Yvan Le Borgne (CNRS,LaBRI,Université de Bordeaux)
• Mireille Bousquet-Mélou (LaBRI, CNRS, U. Bordeaux)
• Henri Derycke (LaBRI)
• Adrian Tanasa (LABRI, univ. Bordeaux)
• Élie de Panafieu (Nokia Bell Labs)
• Jean-Christophe Aval (LaBRI, CNRS)
• Mohamed Lamine Lamali (LaBRI)
• Marni MISHNA (Simon Fraser University / LaBRI)
• Marie-Line Chabanol (Bordeaux)
• Elise Goujard (IMB)
• Sanjay Ramassamy (Département de Mathématiques et Applications, École normale supérieure)
• Camille Male (Institut de Mathématiques de Bordeaux)
• Michael Wallner (LaBRI)
• Valentin Feray (Institut für Mathematik, Universität Zürich)
• Marc Noy (BARCELONA)
• Valérie Berthé (IRIF, CNRS)
• Eric Balandraud (IMB)
• Amélie Trotignon (Institut Denis Poisson, université de Tours et Simon Fraser University)
• Frederique Bassino (LIPN, Université Paris 13)
• Andrea Sportiello (LIPN, Université Paris 13)
• Mathilde Bouvel (Institut für Mathematik, Universität Zürich)
• Igor Kortchemski (CNRS & Ecole polytechnique)
• Frédéric Chapoton (IRMA (UMR 7501))
• Julien Roques (Institut Camille Jordan, Université LYON 1)
• Jacopo Borga (Institut für Mathematik Universität Zürich)
• Sergey DOVGAL (Université Paris 13)
• Luis Fredes (LaBRI)
• Nicolas Pétrélis (LMJL Université de Nantes)
• Nathanaël FIJALKOW (LaBRI)
• Julien Courtiel (GREYC, Université de Caen)
• Andrew Elvey Price (LaBRI, Université de Bordeaux)
• Philippe Marchal (LAGA)
• Alexandre ZVONKINE (LaBRI)
• Sébastien Labbé (LaBRI, CNRS)
• Théo Karaboghossian (Labri, Université de bordeaux)
• Frédéric Chyzak (INRIA)
• Sandro Franceschi (LPSM)
• ALIN BOSTAN (INRIA)
• Cyril Banderier (LIPN/CNRS)
• Jean-François Marckert (LaBRI)
• Olivier Guibert (LaBRI)
• Adrien Boussicault (LaBRI)
• Baptiste LOUF (IRIF)
• Philippe Duchon (LaBRI, université de Bordeaux)
• Axel Bacher (LIPN)
• Norbert Cot (Universite ParisDescartes)
• Arthur NUNGE (irif, Université Paris Diderot - Paris 7)
• Bernard Bercu (Institut de Mathématiques de Bordeaux)
• Jean Betrema (LaBRI*)
• Matthieu Josuat-Vergès (CNRS et LIGM, Université Paris-Est Marne-la-Vallée)
• ISAAC KONAN (IRIF, PARIS DIDEROT)
• Paul Melotti (LPSM)
• Gilles Zémor (IMB)
• Mathieu sablik (IMT)
• Xavier Caruso (IMB)

Organisateurs

• Mireille Bousquet-Mélou
• Auriane Dantes
• Katel Guérin
• Yvan Le Borgne

Soutien financier

• LaBRI
• Projet ANR GRAAL
• OpenDreamKit
• Département Sciences et techniques, Université de Bordeaux
• Bordeaux INP Aquitaine