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

Enregistrement


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.

Transparents


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.

Transparents


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.

Enregistrement


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.

Enregistrement


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)

Enregistrement


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.

Enregistrement


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.

slides Enregistrement


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)

Enregistrement


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

slides


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.


Français English

Groupe

Événements

GT

* Années précédentes

Ressources

edit SideBar