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

Les JCB 2020 ont eu lieu du mercredi 5 au vendredi 7 février 2020. 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.

• Cyril Nicaud (LIGM, Marne-la-Vallée) Synchronisation d’automates aléatoires
  Résumé

  Il y a 50 ans, Cerny a posé une conjecture combinatoire sur les automates, qui n’est toujours pas résolue. Un automate est dit synchronisé quand il existe un mot $u$ et un état $p$ tel que depuis n’importe quel état, si on lit $u$ on arrive en $p$. Sa conjecture est que si l’automate synchronisé possède $n$ états, alors il existe un tel $u$ de longueur au plus $(n-1)^2$. Dans cet exposé, nous nous intéresserons à la version probabiliste de la conjecture de Cerny : on montrera qu’un automate aléatoire est non seulement synchronisé avec forte probabilité (en donnant une autre preuve d’un résultat de Berlinkov), mais qu’en plus la conjecture de Cerny est vraie avec forte probabilité.
• Christophe Cordero (LIGM, Marne-la-Vallée) Combinatoire énumérative des chemins appliquée aux circuits
  Résumé

  Les circuits sont des assemblages planaires d’opérateurs abstraits (appelés générateurs) dotés d’entrées et de sorties. Ils peuvent modéliser, entre autres, des circuits imprimés, des opérations algébriques ou des systèmes de réécriture. Nous allons dénombrer les circuits selon leurs nombres d’entrées et de sorties et selon la nature et le nombre de leurs générateurs. La principale difficulté que nous allons rencontrer provient de l’ambiguïté de la grammaire qui les définit. Nous allons dans un premier temps présenter une nouvelle grammaire non ambiguë qui les engendre. Nous en déduirons une bijection entre les circuits et des familles de chemins colorés en trois dimensions. En étudiant la combinatoire de ces chemins, nous obtiendrons des formules de récurrence, des équations fonctionnelles et des formules closes sur les circuits.
• Élise Goujard (IMB, Bordeaux) Higher genus meanders
  Résumé

  A meander is a topological configuration of a line and a simple closed curve on the plane (the road and the river), or equivalently, a pair of simple closed curves on the 2-sphere, intersecting transversally. Similarly, we define a higher genus meander as a configuration of a pair of simple closed curves on a surface of higher genus. For meanders of fixed topological type (fixed number of minimal arcs), we give asymptotic formula for the number of such meanders as the number of crossings tends to infinity. We also derive similar formula for meanders of genus tending to infinity. The results are based on the interpretation of meanders as square-tiled surfaces with one horizontal and one vertical cylinder and on the recents developments in the couting of such flat surfaces as $g$ tends to infinity. This is a joint work with Vincent Delecroix, Anton Zorich and Peter Zograf.
• Théo Karaboghossian (LaBRI, Bordeaux) Graph insertion operads
  Résumé

  Operads are mathematical structures which have been intensively studied in the context of topology, algebra but also combinatorics. In the last decades, several interesting operads on trees have been defined. Amongst these tree operads, maybe the most studied is the pre-Lie operad PLie. It then seems natural to ask what kind of operads can be defined on graphs and what are their properties. This question also comes from physics, where graph operads are used to encode the combinatorics of the renormalization of Feynman graphs.

  In this talk I explore this question by providing a general way to define graph operads and investigating particularly interesting operads generated in this way.

• Valentin Ovsienko (CNRS, Laboratoire de mathématiques de Reims) $q$-deformed rationals, and $q$-deformed real numbers
  Résumé

  A number of $q$-deformations are known in algebra, geometry and combinatorics. However, $q$-deformations of numbers are only well understood (since Euler and Gauss) for integers. Many classical sequences of integers have interesting $q$-analogues. The best known one is the notion of $q$-binomial coefficients. I will talk of a recent attempt, with Sophie Morier-Genoud, to develop a theory of $q$-deformed rational and real numbers, based on combinatorial properties of continued fractions. A $q$-rational is a ratio of certain polynomials with positive integer coefficients. I will give a combinatorial interpretation of the coefficients and describe some properties, such as total positivity. A $q$-real is understood as a formal power series with integer coefficients. I will give several concrete examples.
• Luca Lionni (IMAPP, Radboud University, Pays-Bas) Iterated foldings of discrete spaces and their limits: candidates for the role of Brownian map in higher dimensions
  Résumé

  Avec J.-F. Marckert, nous avons récemment introduit des familles de graphes aléatoires $(R_n[D],n > 0)$ où $n$ est la taille, et $D$ un autre paramètre. Pour $D=1$, $R_n[1]$ est un arbre planaire uniforme à $n$ arêtes, et pour $D=2$, $R_n[2]$ est une quadrangulation planaire uniforme pointée et enracinée à $n$ faces. Pour ces valeurs de $D$, les graphes convergent donc respectivement vers l’arbre continu aléatoire et la carte brownienne, après des normalisations respectives en $n^{1/2}$ et $n^{1/4}$, pour la topologie de Gromov-Hausdorff. Pour $D>2$, le graphe aléatoire $R_n[D]$ est obtenu par $D-2$ séries d’identifications sur une carte planaire aléatoire, et il converge en loi, après normalisation par $1/n^{1/(2^D)}$, vers un espace continu aléatoire qu’on a nommé $D$-ième feuilletage aléatoire (pour une topologie plus faible que Gromov-Hausdorff). Je présenterai la construction de ces graphes aléatoires et de leurs limites. Cette construction repose sur une nouvelle notion de serpent itéré qui permet de montrer que le diamètre de $R_n[D]$ est asymptotiquement majoré par $n^{1/(2^D)}$ (nous pensons que c’est la bonne échelle). Nous proposons par cette construction une généralisation de la carte brownienne en dimensions supérieures.
• Sebastian Barbieri (LaBRI, Bordeaux) The domino problem is undecidable on surface groups
  Résumé

  The domino problem is a classical decision problem concerning the possibility of tiling a Euclidean plane by a finite number of unit squares which must satisfy local constrains. We study an analogue of this problem for word-hyperbolic groups and show that the domino problem is undecidable for the fundamental group of any closed orientable surface of positive genus. We shall also give a few perspectives that tie this decision problem with a famous open conjecture of Gromov. This is joint work with Nathalie Aubrun and Étienne Moutot.
• Angèle Hamel (Wilfrid Laurier University, Canada) The $e$-positivity of chromatic symmetric functions for certain H-free graphs
  Résumé

  A symmetric function is $e$-positive if it can be written as a positive linear combination of elementary symmetric functions. When Stanley defined chromatic symmetric functions in 1995 he made a conjecture concerning the $e$-positivity of certain claw-free graphs. Here we extend the claw-free idea to consider the $e$-positivity question for chromatic symmetric functions of H-free graphs with H={claw, net} or H ={claw, F}, where F is a four-vertex graph. In a pair of papers we have settled the $e$-positivity of a number of classes of this type of graph and have posed several conjectures. Li and Yang have recently settled some of these conjectures, but some remain open. This is joint work with Chinh Hoang, Owen Merkel, and Jake Tuero.
• Arnaud de Mesmay (LIGM, Marne-la-Vallée) Tightening Curves on Surfaces Monotonically with Applications
  Résumé

  We prove the first polynomial bound on the number of monotonic homotopy moves required to tighten a collection of closed curves on any compact orientable surface, where the number of crossings in the curve is not allowed to increase at any time during the process. The best known upper bound before was exponential, which can be obtained by combining the algorithm of de Graaf and Schrijver [JCTB, 1997] together with an exponential upper bound on the number of possible surface maps. To obtain the new upper bound we apply tools from hyperbolic geometry, as well as operations in graph drawing algorithms-–the cluster and pipe expansions-–to the study of curves on surfaces.

  As corollaries, we present two efficient algorithms for curves and graphs on surfaces. First, we provide a polynomial-time algorithm to convert any given multicurve on a surface into minimal position. Such an algorithm only existed for single closed curves, and it is known that previous techniques do not generalize to the multicurve case. Second, we provide a polynomial-time algorithm to reduce any $k$-terminal plane graph using electrical transformations for arbitrary integer $k$. Previous algorithms only existed in the planar setting when k$$ is at most 4 and all of them rely on extensive case-by-case analysis based on different values of $k$. Our algorithm makes use of the connection between electrical transformations and homotopy moves, and thus solves the problem in a unified fashion.

  Joint work with Hsien-Chih Chang (Duke)

• Baptiste Louf (IRIF, Paris) Limites locales de cartes de grand genre et universalité
  Résumé

  La notion d’universalité est un concept important dans l’étude des cartes combinatoires : on observe des phénomènes similaires pour différents modèles de cartes. L’exemple le plus célèbre est la convergence d’échelle de nombreux modèles de cartes planaires aléatoires vers la carte brownienne.

  En 2012, Benjamini et Curien ont formulé une conjecture sur la limite locale des triangulations de grand genre, que nous avons démontrée en 2019 avec Thomas Budzinski. Dans un deuxième travail, nous étendons l’étude des limites locales en grand genre à une vaste classe de cartes (plus précisément les cartes biparties à degrés prescrits).

  Cet exposé sera une introduction à nos techniques, qui reposent à la fois sur des arguments probabilistes et sur des récurrences énumératives que j’ai obtenues dans un travail indépendant via la hiérarchie de 2-Toda.

• Philippe Ruelle (Université catholique de Louvain) Tangence dans les courbes arctiques
  Résumé

  After a short review of the arctic phenomena and associated arctic curves, I will describe the so-called tangent method that has been used in a number of situations to successfully compute arctic curves. This method, though very efficient, is not yet fully understood, especially its domain of applicability. It is based on two main assumptions, one of them (the weakest one) being a certain tangency property. The talk intends to show how this tangency assumption can be understood, and proved, in a fairly general setting.
• Philippe Nadeau (Institut Camille Jordan, Université Lyon 1) Symétrisation divisée et fonctions quasisymétriques
  Résumé

  La symétrisation divisée est un opérateur linéaire sur les polynômes multivariés. Appliquée aux monômes, elle permet de calculer le volume des permutoèdres généralisés ; appliquée aux polynômes de Schubert, elle répond à un problème de géométrie énumérative. Nous définirons la symétrisation divisée et expliciterons ces deux contextes. Ensuite, nous montrerons que cet opérateur se comporte particulièrement bien vis-à-vis des fonctions quasisymétriques. Cet exposé est basé sur un travail en commun avec Vasu Tewari (UPenn).
• Sébastien Martineau (LPSM, Paris) Percolation arithmétique et le graphon des visibilités
  Résumé

  On dit qu’un point $u$ de $ℤ^d$ est visible depuis le point $v$, également dans $ℤ^d$, si le segment [$u,v$] contient exactement deux points entiers ($u$ et $v$). Si on colorie en blanc les sommets visibles depuis l’origine et les autres en noir, à quoi ressemble ce coloriage vu depuis un point tiré “uniformément au hasard” dans $ℤ^d$ ? Si on tire indépendamment $N$ points “uniformément au hasard” dans $ℤ^d$, peut-on décrire explicitement les probabilités régissant les visibilités mutuelles de ces $N$ points ? Peut-on trouver un énoncé traitant de façon unifiée les deux questions précédentes ? Comment donner un sens précis à tout cela ? Les réponses feront intervenir des notions issues de l’arithmétique, des probabilités et de la combinatoire. Il sera notamment question de convergence de Benjamini–Schramm et de graphons.
• Justine Falque (LRI, Orsay) Classification des groupes P-oligomorphes, conjectures de Cameron et Macpherson
  Résumé

  Étant donné un groupe de permutation infini $G$, on définit la fonction qui à tout entier naturel $n$ associe le nombre d’orbites de sous-ensembles de cardinal $n$, pour l’action induite de $G$ sur les sous-ensembles d’éléments. Cameron a conjecturé que cette fonction de comptage, le profil de $G$, est équivalente à un polynôme si elle est bornée par un polynôme. Une autre conjecture, plus forte, a été émise en 1985 par Macpherson. Elle concerne une certaine structure d’algèbre graduée sur les orbites de sous-ensembles, créée par Cameron, et suppose que si le profil de $G$ est polynomial, alors son algèbre des orbites est de type fini. Après une présentation générale du contexte, l’exposé abordera les outils et raisonnements permettant d’obtenir une classification des groupes de profil polynomial, ainsi que les bénéfices d’une telle classification -– entre autres, une démonstration des deux conjectures.
• Frédéric Chyzak (INRIA Saclay) Explicit generating series for small-step walks in the quarter plane
  Résumé

  Lattice walks occur frequently in discrete mathematics, statistical physics, probability theory, and operational research. The algebraic properties of their enumeration generating series vary greatly according to the family of admissible steps chosen to define them: their generating series are sometimes rational, algebraic, D-finite, differentially algebraic, or sometimes they possess no apparent equation. This has recently motivated a large classification effort. Interestingly, the involved equations often have degrees, orders, and sizes, making calculations an interesting challenge for computer algebra. In this talk, we study nearest-neighbours walks on the square lattice, that is, models of walks on the square lattice, defined by a fixed step set that is a subset of the 8 non-zero vectors with coordinates $0$ or $\pm 1$. We concern ourselves with the counting of walks constrained to remain in the quarter plane, counted by length. In the past, Bousquet-Mélou and Mishna showed that only 19 essentially different models of walks possess a non-algebraic D-finite generating series; the linear differential equations have then been guessed by Bostan and Kauers. In this work, we give the first proof that these equations are satisfied by the corresponding generating functions. This allows to derive nice formulas for the generating functions, expressed in terms of Gauss’ hypergeometric series, to decide their algebraicity or transcendence. (Based on joint work with Alin Bostan, Mark van Hoeij, Manuel Kauers, and Lucien Pech.)

Emploi du temps

Mercredi 5 février

Jeudi 6 février

Vendredi 7 février

Informations pratiques

Accès et logement

Les exposés ont eu lieu dans l’amphithéâtre du LaBRI (bât. A30).

• Accès au LaBRI.
• Plan local des environs du LaBRI. Les stations de tramway les plus proches sont Forum et Béthanie.
• Une liste d’hôtels.

Taxis

• Taxi Talençais : 06 17 82 34 34
• Emile taxi : 06 72 38 82 27
• Taxis Girondins : 05 56 80 70 37

Restaurants

Plan interactif

• Proches du LaBRI: Plan
  • Le Bistro Régent, brasserie, en face du cinéma Gaumont.
  • Yamato, japonais en face du cinéma Gaumont.
  • L’Alcala, pizzeria, sur la place, de l’autre côté de l’arrêt de tram Forum.
  • La Parcelle, bar à vins sympa, charcuterie, fromages. Sur la place, de l’autre côté de l’arrêt de tram Forum.
  • La brasserie du forum, cuisine classique, en face de l’arrêt Forum.
  • Campo Verde, pizzeria, Cours Gambetta au Nord de l’arrêt Forum.
  • Le Carpe Diem, brasserie près de l’arrêt Béthanie.
  • Le 48, boulangerie près de l’arrêt Peixotto.
  • Twist ‘N’ Crêpes, anciennement Le café bleu, crêperie aux couleurs des Beatles un peu au Sud de l’arrêt Forum.
• Près du centre: Plan
  • 5 rue de la Vieille Tour.
  • 22 place des Capucins, pour carnivores.
  • Le Croc Loup, rue du Loup (petit, il fallait réserver, fermé lundi).
  • La Belle Époque, angle sud des quais et des Quinconces.
  • Le Karma, rue du Pas St Georges, cuisine “fusion”.
  • Aux 4 coins du vin, rue de la Devise (très bon bar à vin, assiettes “diététiques” également).
  • A Cantina, restaurant XOR tapas, Corse.
  • Le Petit Commerce, rue du Parlement St-Pierre, restaurant et tapas, poisson & fruits de mer.
  • Elios, rue du Chapeau Rouge, sarde, très copieux.
  • La Brasserie du Sud Ouest, Cours de la Somme.
  • L’Estacade, restaurant sur pilotis, rive droite belle vue sur Bordeaux.
  • Le Café du Port, poissons et fruits de mer, rive droite au niveau du Pont de Pierre.
  • Le Café des Moines, bar à bières.

Participants

• Yvan Le Borgne (LaBRI)
• Sébastien Labbé (LaBRI, CNRS)
• Diego Figueira (LaBRI, CNRS)
• Olivier Guibert (LaBRI, Univ. de Bordeaux)
• Marni MISHNA (LaBRI/ Math, Simon Fraser University)
• Mireille Bousquet-Mélou (CNRS, LaBRI, Bordeaux)
• Jean-Christophe Aval (LaBRI, CNRS)
• Sebastián Barbieri
• Xavier Viennot (LaBRI)
• Elise Goujard (IMB)
• Baptiste Louf (IRIF)
• Eric Balandraud (Institut Mathématiques de Bordeaux)
• Valentin Ovsienko (CNRS, Université de Reims)
• Frédéric Chyzak (INRIA)
• Sébastien Martineau (LPSM)
• Luca Lionni (IMAPP, Radboud University)
• Théo Karaboghossian (LaBRI)
• Philippe Ruelle (IRMP, UCLouvain)
• Philippe Nadeau (Institut Camille Jordan, Université Calude Bernard Lyon 1)
• Christophe Cordero (Université Paris-Est Marne-la-Vallée)
• Julien Courtiel (GREYC, Université de Caen Normandie)
• Philippe Duchon (LaBRI, Université de Bordeaux)
• Philippe Duchon (LaBRI, Université de Bordeaux)
• Nicolas Bonichon (LaBRI - U. Bordeaux)
• Arnaud de Mesmay (CNRS, LIGM)
• Jean-François Marckert (LaBRI)
• Frederique Bassino (LIPN, Université Paris 13)
• Justine Falque (LRI, Université Paris-Sud)
• Luis Fredes (Paris-Saclay)
• Ariane Carrance (Laboratoire de Mathématiques d’Orsay, Paris-Saclay)
• Peter McNamara (LaBRI / Bucknell University)
• Cyril Nicaud (LIGM)
• Hugo Mlodecki (LRI Université Paris-Sud)
• Hugo Mlodecki (LRI Université Paris-Sud)
• Julien ESNAY (IMT Toulouse)
• Angèle Hamel (Wilfrid Laurier University)
• Jean Bétréma (LaBRI)
• Andrew Elvey Price (LaBRI, université de Bordeaux)
• Xavier Caruso (IMB, CNRS)
• Axel Bacher (LIPN, Université Paris Nord)
• Alexandre Zvonkine (LaBRI)
• Marie Albenque (CNRS, LIX)
• Amaury Durand (IMB)
• Sandro FRANCESCHI (LMO)
• Wenjie Fang (LIGM, Université Gustave Eiffel)
• Adrian TANASA (LABRI)
• Guillaume Chapuy (IRIF UMR CNRS 8243)
• Robert Cori (Labri)
• FREDERIC JOUHET (INSTITUT CAMILLE JORDAN)
• Henri DERYCKE (GREYC - Univ. Caen Ndie)
• Khaydar Nurligareev (LIPN, Paris-13)
• Luca De Feo (Inria Saclay)
• Matthieu Josuat-Vergès (IRIF, Université de Paris, CNRS)
• David Wahiche (Institut Camille Jordan)
• Marc Zeitoun (LaBRI, Bordeaux)
• Alin Bostan (INRIA Saclay Île-de-France)
• Andrea Sportiello (LIPN, Universite’ Paris 13)
• Matteo D’Achille (LIPN)
• Jennifer McLoud-Mann (Universite de Bordeaux)
• Casey Mann (Universite de Bordeaux)
• Doriann Albertin (LIGM, UPEM)
• Cyril Banderier (LIPN, CNRS)
• Sophie Juppet (LaBRI)
• Eric Balandraud (IMB)

Organisateurs

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

Soutien financier

• LaBRI
• Département Sciences et techniques, Université de Bordeaux
• Bordeaux INP Aquitaine
• ALEA network Europe
• Projets ANR Aspag, Codys, Combiné
• Institut universitaire de France