Les midi-combi à Nancy

Les midi-combi sont une proposition de petit "groupe de travail", ou "forum de discussion" à Nancy pour celles et ceux qui se reconnaissent (au moins dans une certaine mesure) dans le mot clé "combinatoire". Si vous êtes intéressés pour vous joindre à nous, le calendrier des prochains rendez-vous est ci-dessous. Et vous pouvez envoyer un mail à Mathilde Bouvel pour recevoir les prochaines annonces par mail.

Calendrier des prochains exposés

Lundis 27 janvier et 3 février, à 11h, salle à déterminer

Orateur : Xavier Goaoc (Loria)

Titre : Un zest de combinatoire topologique appliqué à la simplification de formules d'inclusion-exclusion

Résumé : La formule d'inclusion-exclusion classique peut se simplifier considérablement lorsque l'on se restreint à certaines classes de familles d'ensembles. Cela a notamment été exploré dans le cadre géométrique, à commencer par les familles de demi-espaces ou de boules de R^d. Les techniques mélangent combinatoire et topologie.
Dans le premier exposé j'introduirai à cette combinatoire topologique et donnerai une preuve d'un premier résultat : pour toute famille de n disques du plan, il existe une formule d'inclusion-exclusion de taille O(n) qui est calculable en temps O(n log n).
Dans le second exposé, je présenterai une application de l'inclusion-exclusion au problème algorithmique de coloration de graphe et donnerai une preuve que tout hypergraphe admet une formule d'inclusion-exclusion dont la taille dépend de la taille de son diagramme de Venn.

Date à déterminer, courant février ou mars

Orateur : Dorian Perrot (Loria)

Titre : (à venir)

Résumé : (à venir)

Pour la suite, n'hésitez pas à me contacter si vous souhaitez proposer un exposé aux midi-combi. Merci !

Personnes intéressées

Archives

Les anciens du groupe

Houcine Ben Dali

Exposés passés de l'année 2024-2025

Mardi 17 décembre, à 11h, salle C005 du Loria

Orateur : Jean Cardinal (Université libre de Bruxelles)

Titre : Combinatoire des rectangulations

Résumé : Une rectangulation est une décomposition d'un rectangle en un nombre fini de rectangles. Par le biais de relations d'équivalence naturelles, les rectangulations peuvent être considérées comme des objets combinatoires dotés d'une structure riche : congruences de treillis, graphes de flips, polytopes, algèbres de Hopf, etc. Dans cet exposé, nous explorerons la structure des classes d'équivalence suivantes : les rectangulations faibles qui préservent les adjacences entre segments, et les rectangulations fortes, qui préservent les adjacences entre rectangles. Nous décrirons également des réalisations des rectangulotopes faibles et forts : des polytopes de dimension n-1 dont les sommets sont en bijection avec les rectangulations de taille n, et dont les squelettes sont les graphes de flips sur ces rectangulations.
Travaux réalisés en collaboration avec Andrei Asinowski, Stefan Felsner, Eric Fusy, et Vincent Pilaud.

Mardi 26 novembre 2024, à 11h, en salle B013 du Loria

Orateur : Valentin Feray (IECL)

Titre : Sommes de nombres de Catalan, méandres et polynômes en 1/Pi

Résumé : L'objectif de cet exposé est de calculer des sommes infinies faisant intervenir des produits de nombres de Catalan. Ces sommes sont naturellement indexées par des arbres, et apparaissent dans l'étude d'objets combinatoires aléatoires, appelés systèmes méandriques. Après avoir expliqué le contexte, nous donnerons un algorithme récursif permettant de calculer ces sommes : une conséquence est qu'elles sont toutes des polynômes en 1/Pi. Cet algorithme mélange une identité sur les fonctions hypergéométriques due à Gauss, la récurrence quadratique des nombres de Catalan, et des manipulations combinatoires sur les arbres.
Il s'agit d'un travail en collaboration avec Alin Bostan (INRIA Saclay) et Paul Thévenin (Angers).

Mardi 5 novembre 2024, à 11h, en salle B013 du Loria

Oratrice : Marguerite Bin (Loria)

Titre : Deux codages d'arbre pour calculer le volume de trois polytopes

Résumé : Le combinaèdre, un polytope similaire au permutaèdre, peut aussi être écrit comme somme de Minkowski de segments. Cette structure nous permet de réduire le calcul de son volume à une somme sur les arbres étiquetés. On peut alors utiliser le codage de Prüfer (établissant une bijection entre les arbres et les mots) pour réécrire la somme, ce qui permet de la factoriser pour obtenir une formule explicite. On s'intéressera enfin au volume d'un autre polytope qui nécessitera d'introduire un nouveau codage sur les arbres, qu'on explicitera.

Lundi 7 octobre 2024, à **11h15**, en salle C005 du Loria

Oratrice : Mathilde Bouvel (Loria)

Titre : Entre l'ordre de Bruhat et l'ordre faible : l'ordre "du milieu"

Résumé : On définit un ordre partiel P_n sur les permutations de toute taille n fixée, que l'on appelle l'ordre "du milieu". Cet ordre est un proche cousin des célèbres ordre faible et ordre de Bruhat (que l'on présentera sans supposer de connaissance préalable dans l'exposé). Plus précisément, P_n est à la fois un ordre plus fin que l'ordre faible, et un ordre moins fin que l'ordre de Bruhat. On décrira plusieurs interprétations combinatoires de cet ordre, faisant intervenir notamment des séquences d'inversions, et des motifs de permutations. Puis on présentera quelques unes de ses (belles) propriétés, concernant par exemple l'énumération des intervalles de P_n.
Il s'agit d'un travail commun avec Luca Ferrari et Bridget Tenner. Le preprint associé est là.

Exposés de l'année 2023-2024

Lundi 13 novembre 2023, à 11h, en salle C005 du Loria

Orateur : Valentin Feray (IECL)

Titre : Limites en graphon de modèles statiques et dynamiques de cographes aléatoires

Résumé : Par définition, les cographes sont les graphes pouvant être obtenus à partir du graphe à un sommet en itérant l'opération de "duplication" suivante : choisissez un sommet, dupliquez-le (le nouveau sommet a les mà mes voisins que le sommet d'origine), et éventuellement reliez par une arête le nouveau sommet au sommet dupliqué. Les cographes admettent de nombreuses caractérisations équivalentes (par exemple, ils sont exactement les graphes évitant le chemin $P_4$ comme sous-graphe induit) et ont été très étudiés d'un point de vue algorithmique (de nombreux problèmes difficiles NP sont traitables lorsque l'entrée est supposée être un cographe).
Dans cet exposé, nous discutons de propriétés asymptotiques de grands cographes aléatoires, notamment leur limite au sens des "graphons". Nous considérerons trois modèles différents de cographes aléatoires : un modèle statique (distribution uniforme sur les cographes à $n$ sommets), un modèle dynamique avec une taille croissante (où les duplications sont appliquées de manière aléatoire à partir du graphe à un sommet) et un modèle dynamique à taille constante (où des duplications et des suppressions de sommets sont appliquées au hasard à partir de n'importe quel graphe avec $n$ sommets).
D'après des travaux en collaboration avec F. Bassino, M. Bouvel, L. Gerin, M. Maazoun, A. Pierrot et K. Rivera-Lopez.

Mardi 28 novembre 2023, à 11h, en salle B013 du Loria

Orateur : Mario Valencia (Loria)

Titre : The rotation distance and diameter of graph associahedra

Résumé : The associahedron A(G) of a graph G has the property that its vertices can be thought of as the search trees on G and its edges as the rotations between two search trees. If G is a simple path, then A(G) is the usual associahedron and the search trees on G are binary search trees. In this work, we investigate the diameter of graph associahedra as a function of some graph parameters. We give a tight bound of O(m) on the diameter of trivially perfect graph associahedra on m edges. We consider the maximum diameter of associahedra of graphs on n vertices and of given tree-depth, treewidth, or pathwidth, and give lower and upper bounds as a function of these parameters. We also prove that the maximum diameter of associahedra of graphs of pathwidth two is O(nlogn). We also give the exact diameter of the associahedra of complete split and of unbalanced complete bipartite graphs.
This is a joint work with Jean Cardinal (Université Libre de Bruxelles) et Lionel Pournin (Université Sorbonne Paris-Nord)

Vendredi 15 décembre 2023, à 11h, en salle C005 du Loria

Orateur : Manfred G. Madritsch (IECL)

Titre : La méthode du col et les partitions des entiers

Résumé : Dans le présent exposé, nous commençons par une introduction aux fonctions génératrices et aux différentes méthodes permettant d'obtenir des formules asymptotiques pour leurs coefficients. Après une excursion dans les expansions binaires avec restrictions et les nombres catalans, nous introduisons les partitions d'entiers dans des entiers. Autour de ce problème introductif, nous présentons la méthode du col. Ensuite, nous nous limitons aux partitions en puissances d'entiers et aux entiers avec des chiffres manquants. A la fin de l'exposé, nous présentons les travaux en cours et des problèmes ouverts

Lundi 15 janvier 2024, à 11h, en salle C005 du Loria

Orateur : Philippe Chassaing (IECL)

Titre : Formule de Pascal, automates accessibles et chaines de Markov

Résumé : À chaque triangle combinatoire T_{n,k} possédant une formule de Pascal T_{n,k} = a (n, k) T_{n-1, k-1}+ b (n, k) T_{n-1, k} (e. g. Pascal, Stirling, Euler), on peut associer une chaîne de Markov, sur le simplexe S = {(n, k) / 0 ≤ k ≤ n}, liée à un modèle probabiliste classique (marche aléatoire, collectionneur de coupon, restaurant chinois, iDLA). Les simulations font apparaître la convergence des trajectoires de ces chaînes vers des courbes liées aux équations du col des triangles concernés. Les démonstrations de convergence mêlent méthode du col et méthode de Wormald, mais peuvent être simplifiées radicalement dans certains cas à l'aide de la notion statistique d'exhaustivité introduite par Fisher au siècle dernier. Dans le cas Stirling, on expliquera comment cette convergence de trajectoires fournit une interprétation probabiliste élémentaire de l'énumération asymptotique des automates accessibles obtenue par Korsunov dans les années 70.
Ces résultats sont le fruit d'une collaboration avec Jules Flin et Alexis Zevio.

Vendredi 26 janvier 2024, à 11h, en salle C005 du Loria

Orateur : Wolfgang Bertram (IECL)

Titre : Les nombres surréels de Conway (I)

Résumé : Je vais présenter un travail en cours qui porte sur les "nombres de Conway", dits "nombres surréels", voir leur page Wikipedia. Malgré leur nom, ce sont des objets bien réels et fondateurs pour les maths. Je suis en train de développer une approche qui (j'espère) rendra certains aspects de la construction de Conway à la fois plus simple et plus rigoureuse. Ma motivation pour étudier ces questions vient de leur aspect "fondements de maths" (à la fois pédagogique et scientifique), mais il y a aussi un aspect très important combinatoire, qui peut intéresser aussi bien des mathématiciens que des informaticiens. La source la plus importante reste le livre original de Conway "On Numbers and Games" (ONAG), même si le premier livre publié à ce sujet est celui de Donald Knuth : Surreal numbers - how two ex-students turned on to pure mathematics and found total happiness. Dans la suite, Harry Gonshor et Norman Alling ont écrit des livres devenus des sources incontournables à ce sujet, essayant de combler un manque prétendu de rigueur dans l'approche de Conway. Ma propre approche s'inscrit dans cette ligne. Dans ce premier exposé, très généraliste, je vais présenter ma motivation pour m'intéresser à ces objets, et tenter d'expliquer les grandes lignes des travaux de John Horton Conway et de ses successeurs.

Vendredi 9 février 2024, à 11h, en salle C005 du Loria

Orateur : Wolfgang Bertram (IECL)

Titre : Les nombres surréels de Conway (II)

Résumé : Comme précisé ci-dessus, il s'agit d'un travail en cours, et le contenu de ce deuxième exposé sera modulable en fonction des intérêts des auditeurs. D'un coté "fondements de maths", la nouveauté et importance des nombres surréels est ce qu'ils prolongent la théorie des ensembles de Cantor, en particulier la théorie des nombres ordinaux, et l'unifie avec la théorie des nombres réels. Il s'agit bien d'une "théorie de l'infini" hautement originale, et mon objectif est de clarifier son lien avec la théorie des ensembles "classique" ("ZF"). D'un coté "combinatoire", la motivation de Conway vient de la théorie combinatoire des jeux (ONAG, chapitre 1 ; une référence moderne standard est A. Siegel, Combinatorial Game Theory.) Je ne suis pas spécialiste de ce domaine, mais il semble possible d'y étendre mon approche "ensembliste" et de clarifier le lien entre ces théories. Je ne compte pas entrer dans des questions trop techniques pendant ces deux exposés, mais si cela intéresse des auditeurs, on pourra prolonger cette série en un groupe de travail.

Vendredi 23 février 2024, à 11h, en salle C005 du Loria

Orateur : Pierre-Adrien Tahay (Loria)

Titre : Autour des matrices de différence

Résumé : Une matrice de différence est une matrice à valeurs dans un groupe abélien fini telle que la différence entre deux colonnes distinctes contient chaque élément du groupe avec le même nombre d'occurrences. On note D(r,c,G) l'ensemble de toutes les matrices de différence de taille r x c à valeurs dans le groupe G. Dans les années 2010, Lampio et Östergård ont entamé une classification de ces matrices. Pour cela, ils définissent une relation d'équivalence dans l'ensemble de toutes les matrices de différence, qui à partir d'une matrice de différence donnée, en engendre une autre avec les mêmes paramètres (le nombre de lignes, le nombre de colonnes, et le groupe sous-jacent). On peut alors réduire l'étude à celle d'un représentant privilégié pour chaque classe d'équivalence, appelé matrice de différence ordonnée-normalisée, pour étudier l'existence des matrices de différence dans un ensemble D(r,c,G) pour des paramètres r, c et G donnés. Je présenterai différentes constructions de matrices de différence, ainsi que quelques résultats de non-existence qui utilisent des méthodes combinatoires, algébriques et notamment la théorie des corps finis. La classification et l'étude des matrices de différence est un sujet encore très ouvert. L'usage de l'informatique a permis des avancées significatives ces dernières années, notamment dans les travaux de Lampio et Östergård.

Lundi 25 mars 2024, à 11h, en salle C005 du Loria

Orateur : Guilhem Gamard (Loria)

Titre : Couvrabilité en une et deux dimensions

Résumé : Dans cet exposé nous commencerons par présenter quelques notions de combinatoire des mots : mots finis, infinis, périodicité, complexité en facteurs. Nous nous attarderons ensuite sur la notion de couvrabilité : on dit qu'un mot (fini) u couvre un mot (fini ou infini) w si et seulement si w est recouvert d'occurrences de u, éventuellement chevauchantes. Nous verrons les liens entre cette propriété particulières et d'autres plus classiques, comme la périodicité, l'uniforme récurrence, etc.
Dans la deuxième partie de l'exposé, nous nous intéresserons aux mots en deux dimensions, aussi appelés des "images". Toutes les notions classiques de combinatoire des mots se généralisent à la dimension 2, mais diverses complications surviennent. Nous verrons donc comment la notion de couvrabilité change en deux dimensions.

Vendredi 19 avril 2024, à 11h, en salle A008 du Loria

Oratrice : Mathilde Bouvel (Loria)

Titre : Arbres de génération, une méthode pour l'énumération

Résumé : Les arbres de génération ont été définis dans les années 1990, d'abord dans le contexte des permutations évitant des motifs, puis pour un bon nombre d'autres familles d'objets discrets. Un arbre de génération pour une classe combinatoire C est un arbre enraciné infini, dont les noeuds correspondent bijectivement aux objets de C, et où tout objet de taille n apparaît à profondeur n. Les enfants d'un noeud correspondant à un objet c de C sont obtenus en "ajoutant un atome" à c, selon des règles à déterminer en fonction de la classe combinatoire considérée. Ces règles doivent garantir que tout objet de C apparaît une et une seule fois dans l'arbre. Lorsque ce processus de "croissance locale" est suffisamment régulier, il peut être codé par une règle de réécriture concise. Partant de cette règle de réécriture, on peut (parfois) obtenir l'énumération de la classe C. Pour ce faire, on traduit la règle de réécriture en une équation fonctionnelle pour la série génératrice bivariée (ou multivariée) de C, équation que l'on peut (parfois) résoudre grâce à la méthode du noyau. Dans cet exposé, je propose une introduction à cette approche, illustrée par plusieurs exemples (qui concernent principalement les permutations à motifs exclus).

Lundi 6 mai 2024, à 11h, en salle B013 du Loria

(et non le vendredi 3 mai comme annoncé précédemment).

Orateur : Benjamin Testart (Loria)

Titre : Quelques généralisations des arbres de génération.

Résumé : Cet exposé traite de différentes manières de généraliser les constructions dites par "arbre de génération" pour énumérer des objets combinatoires, qui peuvent aboutir à des meilleurs résultats que les constructions classiques. Il est préférable, mais pas nécessaire, d'avoir assisté à l'exposé précédent de Mathilde à propos de ces constructions. On procédera d'abord à quelques rappels sur les arbres de génération. Ensuite, on présentera des généralisations de cette approche, que l'on appliquera à des exemples d'arbres pour certaines familles de séquences d'inversions évitant des motifs (après avoir défini ce que sont les séquences d'inversions et leurs motifs).

Lundi 13 mai 2024, à 11h, en salle A008 du Loria

Orateur : Victor Dubach (IECL)

Titre : Permutations aléatoires et partitions : quelques résultats d'universalité

Résumé : Les permutations sont des objets complexes. Pour mieux les comprendre on peut leur associer des objets plus simples, comme des partitions d'entiers, qui contiennent des informations partielles. Les deux manières usuelles d'associer une partition à une permutation sont via son "diagramme de Robinson-Schensted" (qui contient des informations sur les sous-suites croissantes de la permutation) ou via son "type cyclique" (qui contient la liste des longueurs des cycles de la permutation). On peut alors se demander si ces deux partitions contiennent des informations redondantes, c'est-à-dire si la connaissance de l'une contraint fortement l'autre.
Le but de cet exposé est de répondre (très) partiellement à cette question, quand la taille de la permutation tend vers l'infini. Plus précisément : si on fixe un grand type cyclique arbitraire sans trop de points fixes, et qu'on considère une permutation aléatoire uniforme contrainte à avoir ce type cyclique, alors son diagramme de R-S ressemble fortement à celui d'une permutation uniforme non contrainte. La preuve de ce résultat est technique, mais repose sur une approche géométrique simple pour construire des permutations aléatoires dont on contraint le type cyclique. Cette approche permet d'étudier d'autres statistiques de ces permutations contraintes, comme leur nombre de records ou le nombre d'occurrences de motifs. Basé sur cet article.

Vendredi 31 mai 2024, à 11h, en salle de conférence à l'IECL

Orateur : Xavier Goaoc (Loria)

Titre : Pulvérisation d'hypergraphes (géométriques)

Résumé : Un résultat classique de Sauer-Vapnik-Chervonenkis-Shelah permet de contrôler le nombre d'arêtes d'un hypergraphe au moyen d'un paramètre local, sa "dimension VC". Cela révèle un phénomène plus général : le comportement asymptotique de la "fonction de pulvérisation" ("shatter function") d'un hypergraphe peut être contrôlé à partir d'une majoration non-triviale d'une seule valeur de cette fonction.
Cet exposé proposera une introduction à ces notions et résultats avec quelques illustrations géométriques. J'esquisserai ensuite une construction probabiliste qui a permis de réfuter une conjecture de Hajnal et Bondy, puis quelques pistes d'extensions de ces notions aux familles de permutations. L'exposé ne supposera aucune connaissance préalable.
Cela est basé sur les articles suivants : Article 1, Article 2

Mardi 11 juin 2024, à 11h, en salle C005 du Loria

Orateur : Philippe Chassaing (IECL)

Titre : Riffle Shuffle et triangle d'Euler.

Résumé : On a vu dans un exposé précédent que les formules de Pascal des triangles de Stirling ou de Pascal définissent naturellement des chaînes de Markov, qui se trouvent être les "renversées dans le temps" de processus combinatoires classiques (e.g. la marche aléatoire simple, le collectionneur de coupon, le restaurant chinois). Cela permet une démonstration simple de la convergence en limite hydrodynamique de ces chaînes renversées dans le temps. La chaîne de Markov associée au triangle d'Euler présente un comportement analogue, si l'on en croit les simulations, mais plusieurs différences cruciales ont empêché de démontrer la convergence, et même de conjecturer sa limite. Cet exposé, en explorant les liens entre le triangle d'Euler et les travaux de Diaconis et al. sur le riffle shuffle, ambitionne de proposer et d'étayer une conjecture sur cette limite (travail en cours).

Lundi 24 juin 2024, à 11h, en salle C005 du Loria

Orateur : Florent Koechlin (LIPN, mais anciennement Loria !)

Titre : A canonical tree decomposition for chirotopes

Résumé : Dans cet exposé, je présenterai une notion d'arbre de décomposition d'un ensemble de points dans le plan (plus précisément de son chirotope, la fonction qui encode l'orientation de tout triplet de point de l'ensemble). Cette décomposition, qui s'appuie sur le concept d'ensembles de points s'évitant mutuellement ("mutually avoiding sets"), s'inspire de la décomposition modulaire des graphes. J'expliquerai pourquoi cette décomposition est canonique, et comment elle peut être utilisée pour calculer le nombre de triangulations d'un chirotope à l'aide de sa décomposition. Il s'agit d'un travail commun avec Mathilde Bouvel, Valentin Féray et Xavier Goaoc.