Journées de combinatoire de Bordeaux
12-14 février 2018, LaBRI, Bordeaux

En probabilités géométriques, on étudie des figures géométriques engendrées aléatoirement. Dans cet exposé, on se concentre sur le modèle classique de la mosaïque de Poisson-Voronoi qui est une partition de l'espace engendrée par un ensemble de points aléatoires appelés germes, chaque germe donnant naissance à une zone polyédrique de l'espace appelée cellule. Lorsque l'ensemble des germes a de bonnes propriétés d'homogénéité comme c'est le cas pour un ensemble invariant par translation dans l'espace euclidien, la théorie générale des processus ponctuels permet de calculer les moyennes de certaines caractéristiques géométriques des cellules. Ce n'est plus le cas lorsqu’il y a inhomogénéité de la répartition des germes. On s'intéressera à deux problèmes différents : d'une part, un ensemble de germes dans le plan dont la répartition connaît un “trou”, c'est-à-dire un ensemble convexe compact vide ou que l’on force à être contenu dans une cellule et d'autre part, un ensemble de germes sur une variété riemannienne de courbure non constante. Dans les deux situations, on calculera des moyennes de caractéristiques géométriques (nombre de sommets d'une cellule notamment) dans un cadre asymptotique. L'exposé est basé sur des travaux communs avec Aurélie Chapron (Université Paris Nanterre), Yann Demichel (Université Paris Nanterre) et Nathanaël Enriquez (Université Paris-Sud).

Generalized exponents are important graded multiplicities in representation theory of simple Lie algebras. Notably, they are particular Kazhdan-Lusztig polynomials. In type A, they admit a nice combinatorial description in terms of Lascoux-Schützenberger’s charge statistics on semistandard tableaux. In this talk I will recall their definition and explain how to get similar statistics beyond type A. This will give a combinatorial proof of the positivity of their coefficients but also some other interesting properties. This is a work in collaboration with Cristian Lenart.

Dans cet exposé, nous présenterons quelques résultats concernant l’étude probabiliste de cartes planaires aléatoires. Cette théorie, initiée par Angel et Schramm au début des années 2000, vise à comprendre les propriétés géométriques de cartes planaires aléatoires dont la taille tend vers l’infini. Les travaux de Le Gall et Miermont ont notamment permis de montrer la convergence de plusieurs modèles vers une surface aléatoire universelle, la carte brownienne, qui constitue un analogue du mouvement brownien pour la sphère. Après une introduction à ces résultats, nous nous intéresserons à des cartes planaires aléatoires ayant de grandes faces, appelées cartes stables, qui offrent une géométrie très différente de celle de la carte brownienne.

Les polynômes eulériens sont des objets combinatoires apparaissant dans des contextes à la fois énumératifs et algébriques. Ils sont définis à partir des sous-ensembles des permutations ayant un nombre fixé de descentes. Nous proposons ici une généralisation des polynômes eulériens à partir d'une notion de descente sur des généralisations des permutations, à savoir les permutations segmentées. Ces permutations sont apparues récemment dans une étude combinatoire des probabilités asymptotiquement stables du 2-ASEP. Nos objets ont de nombreuses propriétés en commun avec les polynômes eulériens usuels et nous démontrerons ces propriétés en utilisant une structure algébrique autour des permutations segmentées généralisant celle des fonctions symétriques non-commutatives.

The Tamari lattice is a partial order on Catalan objects (binary trees, Dyck paths, triangulations of polygons...) whose Hasse diagram can be geometrically realized as the graph of a polytope: the associahedron. Préville-Ratelle and Viennot generalized it to the set of lattice paths above a fixed path $v$, giving rise to the $v$-Tamari lattice. Its Hasse diagram can be similarly geometrically realized as the graph of a polyhedral complex, which in the Fuss-Catalan case is a subdivision of an associahedron induced by a tropical hyperplane arrangement. The combinatorics of these objects are easily described by means of $(I,J)$-trees or $v$-trees (non-crossing tree-like tableaux). With the latter we show that the $v$-Tamari lattice can be obtained as the dual of certain subword complex, generalizing a known result for the classical Tamari lattice. This is joint work with Cesar Ceballos and Camilo Sarmiento.

Une surface à petits carreaux est une quadrangulation obtenue en recollant des carrés unité le long des arêtes par translation ou symétrie centrale. Autrement dit, on a une notion bien définie d'horizontale et de verticale partout dans la carte. On fixe un vecteur de “défauts” $(d_1, d_2, ..., d_k)$ et on s'intéresse aux surfaces à petits carreaux dont les degrés des sommets sont tous de valence 4 sauf pour $k$ d'entre eux pour lesquels les degrés sont respectivement $d_1, d_2, ..., d_k$. Ces surfaces à petits carreaux, en particulier le comportement asymptotique de leur nombre, sont intimement liées à la géométrie des surfaces. Le but de mon exposé sera de motiver l'étude des surfaces à petits carreaux par quelques problèmes géométriques puis d'expliquer comment les valeur zêtas multiples s'immiscent dans les calculs concrets de comportements asymptotiques.

Fighting fish are combinatorial structures made of square tiles that form two dimensional branching surfaces. A main feature of these fighting fish is that the area of uniform random fish of size $n$ scales like $n^{5/4}$ as opposed to the typical $n^{3/2}$ area behavior of the staircase or direct convex polyominoes that they generalize. In this talk we concentrate on enumerative properties of fighting fish: in particular we show that the number of fighting fish with $i$ left lower free edges and $j$ right lower free edges is equal to $(2i+j−2)!(2j+i−2)!/(i!j!(2i−1)!(2j−1)!)$.These numbers are known to count rooted planar non-separable maps with $i+1$ vertices and $j+1$ faces, or two-stack-sortable permutations with respect to ascending and descending runs, or left ternary trees with respect to vertices with even and odd abscissa.

We are interested in a proper degeneracy at $q = 0$ of the $q-$deformed rook monoid of Solomon. We show that it is the algebra of a monoid $R_n^0$ namely the 0-rook monoid, in the same vein as Norton’s 0-Hecke algebra is the algebra of a monoid $H_n^0$, which $R_n^0$ contains. We start from presentation of these monoids and show using some explicit algorithm what are their elements by describing them in term of actions. Furthermore the rook monoid happens to be the type $A$ of a family of monoid called the Renner monoids. We extend the algorithms to type $B$ and $D$, and use them to give a good description of these elements and to enumerate them.

En 2015, Jeandel et Rao ont démontré par des calculs exhaustifs faits par ordinateur que tout ensemble de tuiles de Wang de cardinal au plus 10 soit (1) admet un pavage périodique du plan ${Z}^2$ soit (2) n'admet aucun pavage du plan. De plus, ils ont trouvé un ensemble de 11 tuiles de Wang qui pavent le plan mais jamais de façon périodique. Dans cet exposé, nous présenterons une définition alternative des pavages apériodiques de Jeandel-Rao (2015) comme le codage d'une ${Z}^2$-action sur le tore. Nous conjecturons que c'est une caractérisation complète.

Les pavages sont (pour cet exposé) des coloriages de la grille $Z^d$ qui respectent un certain jeu de contraintes locales. Comptez le nombre de manières dont on peut colorier un hypercube de côté $n$, et considérez le taux de croissance exponentiel de ce nombre. Ce taux correspond à une notion d'entropie dans les divers domaines qui s'intéressent à ces objets : thermodynamique pour des modèles de physique statistique, de Shannon en théorie de l'information, topologique en théorie des systèmes dynamiques.

Pour un nombre fini de contraintes et en dimension 1, on connaît une méthode générale pour déterminer ce taux. En revanche, tous les exemples intéressants en dimension 2 ont nécessité des méthodes combinatoires ad hoc complexes, et la grande majorité restent ouverts, sans aucune méthode générale en vue. Ce n'est qu’en 2007 qu’a été montré qu'une telle méthode générale en dimension supérieure ne peut exister (problème indécidable).

Le meilleur espoir semble consister à regarder certaines sous-classes, en particulier sous des hypothèses de mélange (indépendance à longue distance). En collaboration avec Silvère Gangloff, nous avons cherché à quantifier ces hypothèses et à déterminer le seuil en-dessous duquel une méthode générale existe, et au-dessus duquel on peut prouver qu'elle n'existe pas.

Une série entière est dite différentiellement algébrique si elle satisfait à une équation différentielle polynomiale. La sous-classe des séries holonomes (satisfaisant une équation linéaire) bénéficie d'une grande régularité analytique : nombre fini de singularités, croissance bien connue des coefficients... Pour démontrer qu'une série n'est pas holonome, il suffit donc de nier un de ces critères. La classe des fonctions différentiellement algébriques est bien plus “sauvage” et les critères analytiques y sont souvent mis en défaut. Ainsi pour déterminer si une série est différentiellement algébrique, il faut adopter une nouvelle stratégie.

De nombreuses séries génératrices sont solutions d'une équation discrète linéaire : équation p-mahlérienne pour les séries associées à des nombres automatiques ou équation du noyau pour les séries comptant les marches confinées au quart de plan. Dans cet exposé, nous montrerons comment la théorie de Galois des équations discrètes permet de prédire la forme d'une éventuelle relation différentielle algébrique satisfaite par la série et aussi de ramener la question de la dépendance différentielle de la série à l'étude de relations portant uniquement sur les coefficients de l'équation discrète linéaire. Nous montrerons comment cette méthode s'applique aux séries comptant les marches dans le quart plan, dont le noyau est de genre zéro. Si le temps le permet, nous aborderons le cas du genre 1.

Ce travail est en collaboration avec T. Dreyfus (IRMA-Strasbourg), J. Roques (IJF-Grenoble) et M. F. Singer (NCSU-Raleigh).

A pattern of length $k$ is a permutation of the numbers ${1,...,k}$. This is said to be contained in a permutation of $1,...,n$ for $n>k$ if there is some subsequence of the longer permutation which has the same relative order as the pattern. For example the permutation $135462$ contains the pattern $2341$ because $3462$ is a subsequence of $135462$. Conversely, a permutation which does not contain a certain pattern is said to avoid that pattern. In the 1960s Donald Knuth showed that for any pattern $p$ of length 3, the number of permutations of length $n$ which avoid that pattern is given by the $n$th Catalan number. The question of how many permutations of each length avoid a given pattern of length 4 has been solved for 22 out of the 24 patterns, and the two remaining cases, 1324 and 4231, are trivially equivalent to each other. Despite this, according to Doron Zeilberger, not even God knows how many permutations of length 1000 avoid the pattern 1324. I will describe some recent improvements that David Bevan, Robert Brignall, Jay Pantone and I have made on bounding the growth rate on the number of 1324-avoiding permutations. To prove these bounds we utilise a new structural characterisation of 1324-avoiding permutations as a staircase of 1324-avoiding “dominoes”.

Isoradial graphs are embedded planar graphs where faces are inscribed in a circle of radius 1. As the star-triangle transformation preserves isoradiality, isoradial graphs are well suited to study integrable systems of statistical mechanics. In a joint work with Béatrice de Tilière and Kilian Raschel, we study integrable versions of the Ising model and a spanning forest model on these graphs.

These models are both related to a massive Laplacian we introduce on these graphs, for which an explicit formula of the inverse can be derived, generalizing results by Kenyon.

In this talk, we will explain how this formula for the inverse as well as some properties of the integrable models from statistical mechanics are related to another integrability, in discrete differential geometry, as introduced by Bobenko and Suris.

Je ferai une démonstration des fonctionnalités de résolution numérique d'équations différentielles disponibles dans le module ore_algebra pour SageMath, en essayant d'illustrer leur utilité pour traiter des problèmes issus de la combinatoire. En particulier, je montrerai comment déterminer le comportement asymptotique de certaines suites solutions de récurrences linéaires, encadrement numérique du facteur constant compris, de manière automatique et rigoureuse.

Les participants intéressés sont encouragés à venir avec un ordinateur muni d'une version récente de Sage afin de pouvoir reproduire les exemples « en direct ».