2023-2024
Lundi 25 septembre : Ariane Carrance
Titre : Cartes bicolorées à bord alternant : au-delà des constellations
Résumé : Les cartes bicolorées peuvent être comprises comme un cas particulier du modèle d'Ising sur les cartes. Elles contiennent déjà une complexité qui n'est pas présente dans les cartes quelconques, puisque, quand on cherche à énumérer des cartes bicolorées à bord, surgit la question : quelle condition de bord choisir ? Outre la condition monochrome - la plus simple et la plus connue - et sa proche parente la condition de Dobrushin, d'autres conditions, telles que la condition alternante, apparaissent naturellement dans l'étude de modèles de cartes aléatoires. Dans cet exposé, je présenterai d'abord des résultats d'un travail en commun avec Jérémie Bouttier, sur l'énumération de constellations à bord alternant, mettant en évidence des liens combinatoires et géométriques avec la condition monochrome. Je parlerai ensuite d'un projet en cours avec Valentin Baillard et Bertrand Eynard, où nous obtenons des résultats d'énumération pour le bord alternant pour de nouvelles familles de cartes bicolorées, et notamment dans le cas des "quadrangulations d'Ising".
Lundi 2 octobre : Sébastien Labbé
avec repas d'équipe en salle 76 !
Titre : Un q-analogue de la conjecture d'injectivité de Markoff est vrai
Résumé : Les éléments des triplets de Markoff sont donnés par les coefficients de certains produits matriciels définis par des mots de Christoffel, et la conjecture d'injectivité de Markoff, un problème ouvert de longue date, est alors équivalente à l'injectivité sur les mots de Christoffel. Un q-analogue de ces produits matriciels a été proposé récemment, et nous prouvons que l'injectivité sur les mots de Christoffel est valable pour ce q-analogue. Nous étendons également le problème à des mots arbitraires et fournissons une grande famille de paires de mots où l'injectivité ne tient pas.
Travail fait en collaboration avec Mélodie Lapointe and Wolfgang Steiner. La prépublication, acceptée pour publication dans Algebraic Combinatorics, est disponible ici: https://arxiv.org/abs/2212.09852 .
Lundi 23 octobre : Clément Legrand-Duchesne
Titre : Reconfiguration of square-tiled surfaces.
Résumé : A square-tiled surface is a special case of a quadrangulation of a surface, that can be encoded as a pair of permutations in Sn x Sn that generates a transitive subgroup of Sn. Square-tiled surfaces can be classified into different strata according to the total angles around their conical singularities. Among other parameters, strata fix the genus and the size of the quadrangulation. Generating a random square-tiled surface in a fixed stratum is a widely open question. We propose a Markov chain approach using "shearing moves" (natural reconfiguration operation preserving the stratum of a square-tiled surface). In a subset of strata, we prove that this Markov chain is irreducible and has diameter O(n^2), where n is the number of squares in the quadrangulation.
Lundi 6 novembre : Florian Fürnsinn
Titre : On the algebraicity of hypergeometric functions with arbitrary parameters
Résumé : In this talk I will present a complete classification of algebraic (generalized) hypergeometric functions with no restriction on the set of their parameters. It relies on the interlacing criteria given by Christol (1987) and Beukers-Heckman (1989), which I will present, but allows arbitrary complex parameters with possibly integral differences. I will showcase this criterion on various examples with connections to combinatorics and explain how it can be useful in the classification of generating functions. This talk is based on joint work with Sergey Yurkevich.
Lundi 4 décembre : Torsten Mütze
Titre : Kneser graphs are Hamiltonian
Résumé : For integers k>=1 and n>=2k+1, the Kneser graph K(n,k) has as vertices all k-element subsets of an n-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph K(5,2). This problem received considerable attention in the literature, including a recent solution for the sparsest case n=2k+1. The main contribution of our work is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph J(n,k,s) has as vertices all k-element subsets of an n-element ground set, and an edge between any two sets whose intersection has size exactly s. Clearly, we have K(n,k)=J(n,k,0), i.e., generalized Johnson graphs include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.
Lundi 11 décembre : Ludovic Morin
Titre : Probabilité que n points soient en position convexe dans un κ-gone régulier : Résultats asymptotiques.
Résumé : L'étude de la probabilité que des points tirés uniformément et indépendamment dans un domaine convexe d'aire 1 (dans le plan) soient en position convexe, c'est-à-dire forment l'ensemble des sommets d'un polygone convexe, remonte à la fin du 19e siècle et la conjecture de Sylvester pour 4 points, qui fut résolue par Blaschke en 1917. Depuis, des résultats plus généraux pour n points se sont succédés dans le carré, le triangle, le cercle, ainsi que d'autres résultats asymptotiques.
Dans cette présentation je donnerai un équivalent de la probabilité Pn que n points soient en position convexe dans n'importe quel polygone convexe régulier; jusqu'alors la formule la plus précise, due à Bárány (qui tient dans des conditions plus générales toutefois), identifiait la limite n2 Pn1/n.
Bárány a également prouvé qu'un polygone convexe uniforme tiré dans un convexe K converge vers un domaine déterministe. Toujours dans le cas des polygones réguliers, nous présentons des résultats du 2e ordre concernant les fluctuations de l'enveloppe convexe autour de ce domaine.
Lundi 18 décembre : Yvan Le Borgne
Titre : Sur des marches classiques et quantiques dans les arbres soudés
Résumé : Partant de deux arbres binaires complets de hauteur d, certains ont proposé de les souder via une permutation alternant entre leurs feuilles. Un tel graphe peut-être présenté via une vue locale sous la forme d'un oracle renvoyant pour un sommet donné, la liste de ses voisins. Le premier problème est, étant donné l'identifiant d'une racine de l'arbre, de trouver l'identifiant de l'autre racine. En 2003, Childs, Cleve, Deotto, Farhi, Gutmann, Spielman ont obtenu à la fois une borne inférieure exponentielle sur le nombre d'appels à l'oracle pour tout algorithme classique ainsi qu'un algorithme quantique avec un nombre polynomial d'appels. En 2021, Aaronson a conjecturé qu'un avantage quantique pourrait exister pour le second problème consistant à trouver un chemin entre les deux racines ne connaissant qu'une des deux. J'évoquerai des résultats très récents sur ce sujet et aussi nos travaux avec Shrinidhi Teganahally Sridhara dans le prolongement de mon co-encadrement de son stage de M1 via ReLaX de cet été. Nous proposons des analyses de marches classiques pour ce second problème ainsi qu'un algorithme quantique toujours avec un nombre exponentiel d'appels à l'oracle mais atteignant la meilleure borne inférieure classique que nous connaissons.
Lundi 8 janvier : Yvan Le Borgne
Titre : Sur des marches classiques et quantiques dans les arbres soudés - Partie 2
Résumé : Partant de deux arbres binaires complets de hauteur d, certains ont proposé de les souder via une permutation alternant entre leurs feuilles. Un tel graphe peut-être présenté via une vue locale sous la forme d'un oracle renvoyant pour un sommet donné, la liste de ses voisins. Le premier problème est, étant donné l'identifiant d'une racine de l'arbre, de trouver l'identifiant de l'autre racine. En 2003, Childs, Cleve, Deotto, Farhi, Gutmann, Spielman ont obtenu à la fois une borne inférieure exponentielle sur le nombre d'appels à l'oracle pour tout algorithme classique ainsi qu'un algorithme quantique avec un nombre polynomial d'appels. En 2021, Aaronson a conjecturé qu'un avantage quantique pourrait exister pour le second problème consistant à trouver un chemin entre les deux racines ne connaissant qu'une des deux. J'évoquerai des résultats très récents sur ce sujet et aussi nos travaux avec Shrinidhi Teganahally Sridhara dans le prolongement de mon co-encadrement de son stage de M1 via ReLaX de cet été. Nous proposons des analyses de marches classiques pour ce second problème ainsi qu'un algorithme quantique toujours avec un nombre exponentiel d'appels à l'oracle mais atteignant la meilleure borne inférieure classique que nous connaissons.
Lundi 15 janvier : Hadrien Notarantonio
Titre : [ddesolver] A Maple package for Discrete Differential Equations.
Résumé : Les équations différentielles discrètes sont des équations fonctionnelles reliant algébriquement une série formelle F(t, u) à coefficients polynomiaux en une variable "catalytique" u, avec des spécialisations de cette série par rapport à la variable u. De telles équations apparaissent en combinatoire énumérative, par exemple dans l'énumération de cartes. Mireille Bousquet-Mélou et Arnaud Jehanne ont montré en 2006 que lorsque ces équations sont de type point fixe en F, alors F est une série algébrique. Dans le même article, ils ont proposé une méthode systématique pour calculer les polynômes annulateurs de ces séries. Avec Alin Bostan et Mohab Safey El Din, nous avons récemment conçu de nouveaux algorithmes efficaces pour calculer ces témoins d'algébricité. Dans cet exposé, je présenterai le premier package Maple dédié à la résolution de ces DDEs, les algorithmes sur lesquels ce package repose, ainsi que des résultats pratiques.
Lundi 22 janvier : Xavier Bressaud
Titre : Combinatoire de la marche aléatoire des prisonniers : fraction continues, entropie et modèle de la glace.
Résumé : Pour chaque entier K, on définit SK l'ensemble des chemins de longueur K et de pas +1 ou -1 dans ZK. La marche aléatoire des K prisonniers est une marche aléatoire sur cet ensemble SK . Emmanuel Boissard, Serge Cohen, Thibault Espinasse et James Norris ont montré que les trajectoires du premier prisonnier se comportent globalement comme des marches aléatoires simples de variance inversement proportionnelle à la longueur K de la chaîne. L'enjeu est de comprendre ce qui se passe lorsque K tend vers l'infini : le comportement limite du premier prisonnier est "sous diffusif" mais on ne sait pas bien quantifier cette assertion.
Nous verrons comment on peut définir un processus limite naturel. Notamment, nous montrerons comment le calcul de sa probabilité de transition fait apparaître des fractions continues.
Cette famille de processus peut être vue comme une famille de marche aléatoires sur le graphe des configurations du modèle de la glace (carré(e)) (ou modèle à 6 vertex). Nous terminerons en expliquant comment faire le lien en vue d'exploiter cette connexion.
(Travail commun avec Serge Cohen, IMT/UT3)
Lundi 29 janvier : Alexandre Zvonkine (LaBRI)
Titre : Sur une famille de cartes planaires presque régulières.
Résumé : Il s'agit de cartes bicoloriées à n=4k+1 arêtes avec l'assortiment de degrés suivant: -- tous les sommets noirs sont de degré 4, sauf un, qui est de degré 1; -- tous les sommets blancs sont de degré 2, sauf un, qui est de degré 1; -- et toutes les faces sont de degré 4, sauf une, qui est de degré 1.
Déjà, la question d'énumération se pose. Par exemple, il y a deux cartes pour n=5; une seule pour n=9; il n'existe pas de cartes de ce type avec n=21; il y en a trois pour n=25; quatre pour n=65; pas de cartes de ce type pour n=69; etc. La réponse à la question énumérative est beaucoup plus intéressante qu'on n'y pense.
Ces cartes possèdent aussi d'autres propriétés remarquables. Par exemple, on peut les composer, et cette opération est commutative.
Lundi 12 février : Gábor Hetyei
Titre : Étiquetage des régions dans les arrangements d’hyperplans.
Résumé : L’énumération du nombre de régions dans les arrangements d‘hyperplans a fait l’objet de nombreux travaux en particulier ceux de Pak, Postnikov et Stanley, Athanasiadis et Linusson, Hopkins et Perkinson sur des arrangements dits graphiques. Ces arrangements sont définis par des équations ne contenant que 2 variables. Je me propose de présenter une technique permettant d’étiqueter les régions de plusieurs arrangements classiques (arrangement de Shi étendu, Fuss-Catalan) en utilisant deux résultats. D'une part une variante du Lemme de Farkas donnant des conditions d’existence de solutions dans des inéquations linéaires et d’autre part la décomposition en cycles des flots dans un graphe.
Lundi 19 février : Philippe Duchon
Titre : Génération aléatoire à la Boltzmann: autour du produit de Hadamard
+ Repas d'équipe en salle 76
Résumé : Pour la génération aléatoire d'objets combinatoire, la "méthode de Boltzmann" est une méthode assez générique dans laquelle on génère des objets dont la taille n'est pas directement choisie, elle est elle-même aléatoire selon une distribution qui n'est pas arbitraire et dépend d'un paramètre (et, à taille donnée, l'objet obtenu est uniforme). Le choix du paramètre permet, dans les bons cas, de "viser" une taille moyenne choisie.
Une caractéristique intéressante de la méthode est que pour un certain nombre de constructions classiques en combinatoire (produits, séquences, ensembles...), les générateurs de Boltzmann se composent simplement. À partir d'une spécification de la famille d'objets au moyen de ces constructions, on peut construire quasi automatiquement des générateurs selon la loi de Boltzmann.
Une construction qui n'entre pas dans la panoplie classique est celle du produit de Hadamard de deux familles d'objets: un objet du produit est simplement composé d'un objet de chaque famille, contraints à être de même taille. En génération aléatoire à taille fixe, c'est un non-problème; pour la loi de Boltzmann, c'est moins évident.
En partant d'un algorithme de Sportiello, je discuterai d'optimisations possibles, notamment au niveau du choix des paramètres. (Travail très en cours)
(Vacances scolaires)
Lundi 4 mars : Anna Vanden Wyngaerd
Titre : A sandpile model for the shuffle theorem
Résumé : The shuffle theorem is one of the most famous results in algebraic combinatorics of the last decade. Conjectured in 2001 by Haglund, Haiman, Loehr, Remmel and Ulyanov and proved in 2016 by Carlsson and Mellit, this theorem provides an explicit combinatorial formula for the symmetric function nabla(e_n); also known as the Frobenius characteristic of the diagonal coinvariants. In this work, we provide an entirely different combinatorial model for the same function, using recurrent configurations of the sandpile model on a certain class of graphs. In our formula, we use the classic level statistic (related to the number of grains in the configuration), and a new statistic we call the delay. The proof of our result is a bijective combinatorial one, relating sandpile configurations to labelled Dyck paths, as they appear in the shuffle theorem.
joint work with: Michele D'Adderio, Alessandro Iraci, Mark Dukes, Yvan Le Borgne, Alexander Lazar
Lundi 18 mars : Sébastien Labbé
Titre : Les petits ensembles de tuiles de Wang apériodiques
Résumé : Dans ce premier exposé d'une série de deux, nous présenterons les plus petits ensembles connus de tuiles de Wang apériodiques et nous rappellerons leurs propriétés. Plus précisément, nous présenterons les ensembles suivants:
- L'ensemble de 16 tuiles de Wang proposé par Ammann dans les années 1980.
- Les ensembles de 14 et 13 tuiles de Wang proposés par Kari et Culik dans les années 1990.
- Le plus petit ensemble de tuiles de Wang apériodique découvert par Jeandel et Rao en 2015.
Ces trois ensembles ont des propriétés différentes. En particulier:
- Les tuiles d'Ammann sont auto-similaires, mais pas les autres.
- Les étiquettes des tuiles de Kari et Culik satisfont à des équations, mais pas les autres.
- L'ensemble des pavages avec les tuiles de Kari et Culik est d'entropie strictement positive, mais pas les autres.
- Les pavages de Jeandel-Rao sont expliqués par une partition polygonale, mais a priori pas les autres.
Ces propriétés très différentes rendent difficile la création d'une théorie unifiée permettant d'expliquer tous les ensembles de tuiles apériodiques.
support pdf Enregistrement Zoom
Lundi 25 mars : Sébastien Labbé
Titre : Tuiles de Wang associées aux nombres métalliques
Résumé : Pour chaque entier positif \(n\), nous introduisons un ensemble \(\mathcal{T}_n\) composé de \((n+3)^2\) tuiles de Wang (carrés unitaires avec des bords étiquetés). Nous représentons un pavage par des translations de ces tuiles comme une fonction \(\mathbb{Z}^2\to\mathcal{T}_n\) appelée configuration. Une configuration est valide si le bord commun des tuiles adjacentes a la même étiquette. Pour chaque entier \(n\geq1\), nous considérons le sous-décalage de Wang \(\Omega_n\) défini comme l'ensemble des configurations valides sur les tuiles \(\mathcal{T}_n\).
La famille \(\{\Omega_n\}_{n\geq1}\) élargit la relation entre les entiers quadratiques et les tuiles apériodiques au-delà de l'omniprésent nombre d'or, car la dynamique de \(\Omega_n\) implique la racine positive \(\beta\) du polynôme \(x^2-nx-1\). Cette racine est parfois appelée \(n\)-ième nombre métallique, et en particulier, le nombre d'or lorsque \(n=1\) et le nombre d'argent lorsque \(n=2\).
La famille rassemble les caractéristiques des petits ensembles apériodiques de tuiles de Wang. Lorsque \(n=1\), l'ensemble de tuiles de Wang \(\mathcal{T}_1\) est équivalent à l'ensemble apériodique d'Ammann de 16 tuiles de Wang. Les tuiles de \(\mathcal{T}_n\) satisfont des versions additives d'équations vérifiées par les ensembles apériodiques de Kari-Culik de 14 et 13 tuiles de Wang. Les configurations de \(\Omega_n\) sont également les codages d'une action de \(\mathbb{Z}^2\) sur un tore à 2 dimensions par une partition polygonale comme l'ensemble apériodique de Jeandel-Rao de 11 tuiles de Wang.
Les tuiles peuvent être définies comme les différentes instances d'une puce informatique de forme carrée dont les entrées et les sorties sont des vecteurs entiers à trois dimensions. Il existe une fonction facteur presque partout injective \(\Omega_n\to\mathbb{T}^2\) qui commute l'action de décalage sur \(\Omega_n\) avec les translations horizontales et verticales par \(\beta\) sur \(\mathbb{T}^2\). La fonction facteur peut être explicitement définie par la moyenne des étiquettes supérieures de la rangée de tuiles passant par l'origine, comme dans les exemples de Kari et Culik.
Nous montrons également que \(\Omega_n\) est auto-similaire, apériodique et minimal pour l'action de décalage. De plus, il existe une partition polygonale de \(\mathbb{T}^2\) dont nous montrons qu'elle est une partition de Markov pour une \(\mathbb{Z}^2\)-action sur le tore. La partition et les ensembles de tuiles de Wang sont symétriques, ce qui les rend, comme les tuiles de Penrose, dignes d'intérêt.
Les détails peuvent être trouvés dans les prépublications disponibles à arXiv:2312.03652 (partie I) et arXiv:2403.03197 (partie II). L'exposé présentera une vue d'ensemble des principaux résultats.
Lundi 8 avril : Yvan Le Borgne
Titre : Une approche de la causalité
Résumé : Cette proposition de petite école de combinatoire sera initiée par une première séance traitant explicitement un exemple dans le cadre de la théorie de Pearl sur la causalité. Si le temps le permets, et je ne parle pas de la météo, une première liste de théorèmes sera énoncée en fin de séance pour donner un premier aperçu de la portée de cette approche. Les preuves de ces théorèmes sont susceptibles d'être développées dans les séances suivantes. Ce contenu est adapté d'un enseignement de 26h en deuxième année d'école d'ingénieur en informatique donné depuis septembre 2022 ainsi que d'un cours de 12h donné cette année à l'EDMI.
Lundi 29 avril : Robert Cori
Titre : Un polynôme à la Whitney pour les hypercartes.
Résumé : Travail en commun avec G. Hetyei. Associer un polynôme à un graphe a été un moyen de fournir un outil algébrique pour étudier des objets combinatoires. Dès 1932 Hassler Whitney a introduit des coefficients sur un graphe qui permettent de définir un polynôme à deux variables. Il permet de calculer le nombre de colorations de ce graphe. William Tutte a plus tard utilisé un changement de variables pour introduire un nouveau polynôme qui a connu plus de célébrité. Avec Jean-Guy Penaud nous avons introduit en 1980 une notion de raffinement sur les hypercartes (représentation topologique des hypergraphes), elle nous a permis de nous pencher sur des hyperarbres couvrants de celles-ci. Très récemment nous avons repris cette notion avec Gabor Hetyie pour introduire un polynôme associé à une hypercarte, lorsque cette hypercarte est une carte ce polynôme est celui introduit par Whitney pour le graphe représenté par la carte. Le but de cet exposé est de vous intéresser à la question que nous nous posons aver Gabor sur le polynôme obtenu en effectuant sur notre polynôme le même changement de variables que celui effectué par W.Tutte.
Lundi 6 mai : Yvan Le Borgne
Titre : Une approche de la causalité (suite)
Résumé : Après l'exemple de la première séance, nous aborderons les fondements techniques de cette approche. Cela conduira à se demander comment la forme des hypothèses peut induire une représentation efficace de lois de probabilités. Dans ce contexte nous constaterons que le calcul efficace des loi marginales s'avère délicat en toute généralité. Si le temps de le permets, nous aborderons un algorithme dans certains cas et une heuristique dans le cas général, permettant l'évaluation de marginales conditionnelles. Enfin nous verrons comment des notions de théorie des graphes permettent de caractériser certaines indépendances conditionnelles qualifiées de génériques.
Lundi 13 mai : Xavier Caruso double exposé, 9h30 - 11h45, dans l'amphi du LaBRI
- première partie: 9h30 - 10h30
- entracte: 10h30 - 10h50
- seconde partie: 10h50 - 11h50
Titre : Sur l'algébricité des solutions des équations différentielles linéaires
Résumé : En règle générale, les solutions d'équations différentielles linéaires sont des fonctions transcendantes, quand bien même les coefficients de l'équation sont des polynômes ou des fractions rationelles. Il existe toutefois de cas où des équations différentielles d'intérêt possèdent des solutions algébriques : ce type de phénomènes n'est pas anodin et se rencontre dans différentes branches des mathématiques, incluant notamment la combinatoire et la théorie des nombres. Dans cet exposé, j'expliquerai comment l'algébricité ou la non-algébricité des solutions peut se détecter à l'aide de méthodes arithmétiques. Ceci nous conduira, en particulier, à énoncer et discuter la célèbre conjecture de Grothendieck-Katz.
Pour approfondir, vous pouvez lire A. Bostan, X. Caruso, J. Roques "Algebraic solutions of linear differential equations: an arithmetic approach".
Lundi 27 mai :
PEC (9h30): Yvan Le Borgne
Titre : Une approche de la causalité (épisode 3)
Résumé : Après avoir brièvement rappelé les énoncés de la séance précédente nous nous attèlerons à leur preuve.
GT (10h45): Mark Dukes
Titre : Weak and difference ascent sequences, and related combinatorial structures
Résumé : Let a=(a_1,a_2,...,a_n) be a sequence of nonnegative integers. The ascent set of the sequence a, Asc(a), consists of all indices k where a_{k+1}>a_k. An ascent sequence is sequence, a, where the growth of the a_k is bounded by the elements of Asc(a). These sequences were introduced by Bousquet-Melou, Claesson, Dukes and Kitaev and have many wonderful properties. In particular, they are in bijection with permutations avoiding a particular bivincular pattern, unlabeled (2+2)-free posets, certain upper-triangular nonnegative integer matrices, and a class of matchings.
A weak ascent of a is an index k with a_{k+1} >= a_k and weak ascent sequences are defined analogously to ascent sequences. These were introduced and studied by Benyi, Claesson and Dukes (2022) and shown to have a similarly rich collection of correspondences. Building on this, a further generalization was proposed in Dukes and Sagan (2023) and these are termed "difference d-ascent sequences". Properties of the corresponding difference ascent sequences are that several mappings from the weak case can be extended to bijections for general d, while the extensions of others continue to be injective (but not surjective).
This talk will present an overview of the recent results on weak and difference ascent sequences. It is joint work with Beata Benyi, Anders Claesson, and Bruce Sagan.
Lundi 3 juin : Guillaume Chapuy
Titre : Sur la normalisation des intervalles de Tamari aléatoires et des bois de Schnyder des triangulations aléatoires (avec une astuce D-finie asymptotique)
Résumé : On considère un intervalle de Tamari de taille n (c'est-à-dire une paire de chemins de Dyck qui sont comparables pour la relation de Tamari) choisi uniformément au hasard. On montre que la hauteur d'un sommet uniformément choisi sur le chemin supérieur ou inférieur varie comme n^{3/4}, et a une loi limite explicite. Par la bijection de Bernardi-Bonichon, ce résultat décrit également la hauteur des points dans les arbres canoniques de Schnyder d'une triangulation plane aléatoire uniforme de taille n. La solution exacte du modèle est basée sur des équations polynomiales avec une et deux variables catalytiques. Pour prouver la convergence à partir de la solution exacte, on utilise une version du "pompage des moments" basée sur la D-finitude, qui est essentiellement automatique et devrait s'appliquer à de nombreux autres modèles. Je ne crois pas avoir vu cette astuce simple utilisée auparavant. Il serait intéressant d'étudier l'universalité de cette convergence pour les arbres de décomposition associés aux équations de Bousquet-Mélou--Jehanne positives.
Lundi 10 juin : Jean-Sébastien Sereni (exposé commun CI-GO)
Titre : Vector spaces spanned by Tutte polynomials
Résumé : How much "typical" are Tutte polynomials of matroids among other bivariate polynomials? We will address this question by considering the dimension of the subspace generated by Tutte polynomials of matroids (of given size and rank) as a measure of "typicality". I will present the exact dimension for various classes of matroids (all, graphic, connected, loopless), along with explicit bases and connections between the spaces, providing a surprising answer to a readily understood question.
The talk is based on a joint work with Andrew Goodall and Florent Jouve.
Lundi 17 juin : Craig S. Kaplan
Titre : Detecting isohedral polyforms with a SAT solver
Résumé : I show how to express the question of whether a polyform tiles the plane isohedrally as a Boolean formula that can be tested using a SAT solver. This approach is adaptable to a wide range of poly- forms, requires no special-case code for different isohedral tiling types, and integrates seamlessly with existing software for computing Heesch numbers of polyforms.
Lundi 8 juillet: O. Fontaine, J. Schabanel, J.-F. Marckert
- 09h30-10h00: Oscar Fontaine Using Delaunay triangulation to enumerate saddle connections
- 10h00-10h30: Juliette Schabanel Bijection « slit and sew » pour les cartes biparties planaires à degrés prescrits.
- 10h45-11h45: Jean-François Marckert La limite continue de l'arbre couvrant minimal d'un graphe complet
Orateur: Oscar Fontaine
Titre: Using Delaunay triangulation to enumerate saddle connections
Présentation: Fontaine-2024-07-08.pdf
Résumé: A translation surface is a surface obtained by gluing finitely many euclidian polygons along their edges using translations. Outside the vertices of the polygons, the surface is locally isometric to the Euclidean plane. A saddle connection is a straight line segment in a translation surface whose two ends are conic singularities. It is a result of H. Masur that the number of saddle connections of length at most R is \Theta(R^2). We study the algorithmic problem of enumerating the saddle connections in a given translation surface.
A naive enumeration algorithm allows to list saddle connections in \Theta(R^3). A more sophisticated method using Delaunay triangulations shows that one can achieve the optimal \Theta(R^2) for some specific surfaces.
Oratrice: Juliette Schabanel
Titre : Bijection « slit and sew » pour les cartes biparties planaires à degrés prescrits.
Présentation: Schabanel-2024-07-08.pdf
Résumé : Plusieurs familles de cartes comme les cartes biparties ou les triangulations, comptées par taille et genre, admettent des formules de récurrence remarquablement simples obtenables à partir d’équations issues de hiérarchies intégrables (KP/Toda). Malgré leur simplicité, on ne sait prouver ces formules de façon combinatoire que dans des cas très particulier, comme le cas planaire ou unicellulaire. Dans cet exposé, je présenterai une bijection expliquant le cas planaire d’une formule de récurrence pour les cartes biparties à faces de degrés prescrits, obtenue par Baptiste Louf via la hiérarchie Toda.
Orateur: Jean-François Marckert
Titre: La limite continue de l'arbre couvrant minimal d'un graphe complet. Travail commun Nicolas Broutin (Université Sorbonne), JF Marckert (LaBRI)
Résumé: On considère le graphe complet à n sommets K_n , dont les arêtes sont munies de poids aléatoires indépendants, mettons, uniformes sur [0,1] . On définit alors le poids d'un arbre (inclu dans K_n ) comme étant la somme des poids des arêtes qu'il contient; l'arbre couvrant minimal Tn est l'arbre couvrant de K_n de poids minimal. Il est presque sûrement bien défini, et aléatoire, ça va sans dire; et ajoutons qu'une fois qu'on a trouvé T_n , on le regarde comme un arbre combinatoire, sans poids, et on se demande à quoi il ressemble... sa loi, son échelle, sa forme, et les limites de celles-ci, lorsque n tend vers l'infini.
Addario-Berry, Broutin, Goldschmidt et Miermont, en 2017, on démontré que si on normalise les distances d_{T_n}(.,.) dans T_n par n^{1/3} , alors, (T_n,d{Tn}(.,.)/n^{1/3}) , vu comme espace métrique aléatoire, possède une limite en loi: un arbre continu aléatoire. L'argument de AB-B-G-M est un argument de compacité, et seule l'existence de la limite, et certaines de ses propriétés sont obtenues (c'est un arbre binaire de dimension de Minkowski 3), par contre, la limite n'est pas identifiée.
Dans ce travail, nous identifions la limite, et nous l'appelons "l'arbre parabolique brownien". Il s'agit d'un nouvel objet, construit à l'aide des minorants convexes d'un mouvement brownien avec drift parabolique (l'ensemble des minorants convexes de la courbe sur [0,x] , pour tout x ).
Le but de l'exposé est de présenter cet objet, et d'expliquer, à l'aide principalement d'argument probabilisto-combinatoire, pourquoi il apparaît comme limite de l'arbre couvrant minimal.