Programme

Les exposés commenceront le mercredi à 9 heures pour se terminer le vendredi à 12h. Le mercredi et le jeudi, les exposés finiront à 17 heures.

Le programme est également disponible ici au format pdf.

Mercredi 5 février

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

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.

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.

Repas salle 76, LaBRI

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.

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.

Résumé

Avec J.-F. Marckert, nous avons récemment introduit des familles de graphes aléatoires $(R_n[D],n > 0)$$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.

Jeudi 6 février

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.

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.

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)

Repas salle 76, LaBRI

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.

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.

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

Vendredi 7 février

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.

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.

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