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


Français English

Groupe

Événements

GT

* Années précédentes

Ressources

edit SideBar