10 octobre 2024
- Nicolas Broutin (LPSM)
Minorants convexes, processus de fragmentation/coalescence et limites d’échelle
Je présenterai une manière de construire des arbres aléatoires basée sur les minorants convexes de fonctions (aléatoires). Dans le cas Brownien, cette procédure est reliée au coalescent additif et à l'arbre continu Brownien, c'est-à-dire la limite d'échelle d'arbres uniformes, et de la fragmentation naturelle qui consiste à retirer les arêtes dans un ordre aléatoire.
En modifiant un peu la fonction de départ, on obtient un arbre lié au coalescent multiplicatif (graphes aléatoires) et à l'arbre couvrant minimum d'un graphe complet pondéré aléatoirement. Cette construction conduit aussi à la définition naturelle de nouveaux processus de coalescence/fragmentation liés à des graphes aléatoires contraints et/ou à la percolation d'invasion avec sources multiples.
L'exposé sera basé sur des travaux en commun avec J.-F. Marckert d'une part et Arthur Rousseau d'autre part.
- Marthe Bonamy (LaBRI)
One (graph) minor to rule them all
Robertson, Seymour and Thomas proved in 2006 that every planar graph on n vertices is a minor of the 2n*2n square grid. This theorem is notably convenient in proving that any graph not containing a given planar graph as a minor has bounded treewidth. After a gentle introduction to graph minors, I will discuss the equivalent of grids for classes other than planar graphs.
- Florent Hivert (LISN)
Réalisation diagrammatique de l’algèbre d’Okada et correspondance de Fomin du treillis de Young-Fibonacci
Il est bien connu que le treillis de Young peut s'interpréter comme le diagramme de Bratelli des groupes symétriques, décrivant, par exemple, comment les représentations irréductibles se restreignent de S_n à S_{n-1}. En 1975, Stanley a découvert un treillis similaire appelé treillis de Young-Fibonacci qui a été interprété comme le diagramme de Bratelli d'une famille d'algèbres par Okada en 1994.
Dans cet exposé, nous utilisons un système de réécriture sur des configurations de boucles pour réaliser l'algèbre d'Okada et son monoïde
associé grâce à une version étiquetée des diagrammes d'arcs du monoïde de Jones et de l'algèbre de Tempeley-Lieb. Ceux-ci nous permettent de prouver en toute généralité que l'algèbre d'Okada est de dimension n! — la preuve d'Okada n'étant valide que dans le cas semi-simple. En particulier, nous interprétons la bijection naturelle entre les permutations et les diagrammes d'arcs comme une instance de la correspondance de Robinson-Schensted-Fomin associée au treillis de Young-Fibonacci. Ces constructions possèdent de nombreuses applications : par exemple, on peut prouver que le monoïde est apériodique et décrire ses relations de Green. En relevant ces dernières à l'algèbre nous en construisons une base cellulaire.
Travail en collaboration avec Jeanne Scott.
5 décembre 2024
- Bram Petri (IMJ-PRJ, Sorbonne Université)
Subgroup growth of right-angled groups
The number of subgroups of bounded index of any finitely generated group is finite. This leads to the question how, given a group, this number of subgroups grows as a function of the index and which information about the group is encoded in this sequence of numbers. I will talk about these questions in the context of right-angled Artin and Coxeter groups. I will discuss what is known and also highlight some of the many things we don't know. This will be based on joint work with Hyungryul Baik and Jean Raimbault.
- Eleanor Archer (Cérémade, Université Paris-Dauphine)
Catalan percolation
Catalan percolation is a model introduced by Gravner and Kolesnik (2023) to represent the effect of censorship on the spread of information in a network. In the model, we consider a graph on the positive integers {1, ..., n}. All (undirected) edges {i, j} are independently declared open with probability p, and otherwise closed (or censored). Given this initial randomness, the dynamics are then defined deterministically as follows: all nearest-neighbour edges of the form {i, i + 1} are initially declared occupied, then at each step an open edge {i, j} is declared occupied if there exists a pair of edges {i, k} and {k, j} with i < k < j that are both occupied. Closed edges can never become occupied. It was shown by Gravner and Kolesnik that this model undergoes a constant order phase transition in terms of the final occupation density of long open edges. In this talk we will discuss some non-trivial bounds on the critical probability, on the one hand using a comparison with Catalan structures, and on the other hand using a coupling with an oriented percolation model. Based on joint work with Ivailo Hartarsky, Brett Kolesnik, Sam Olesker-Taylor, Bruno Schapira and Daniel Valesin.
- Frédéric Chapoton (IRMA, Strasbourg)
Sur une combinatoire associée à chaque arbre d'ensembles
À chaque arbre enraciné fini dont les sommets sont décorés par des ensembles, on associe un polytope et le poset de ses points entiers. Un cas particulier donne un poset de cardinal Catalan qui semble avoir des relations étranges avec les treillis de Tamari et les partitions non-croisées. En particulier, les séries génératrices des nombres de Möbius sont reliés par une involution relativement mystérieuse. Pour les arbres d'ensembles de forme linéaire, on conjecture une symétrie inattendue entre polynôme d'Ehrhart et polynômes Zêta.
6 février 2025
- Baptiste Louf (IMB, Bordeaux)
Counting with random walks
We are interested in an enumerative problem, namely counting geometric objects called combinatorial maps, which can be parametrized by two numbers: their size, and a topological parameter called the genus. We are looking for an asymptotic estimate of the number of these objects when both the size and the genus go to infinity. While enumeration in one parameter is a very well studied topic with many powerful tools available, this problem is a case of bivariate enumeration, is a rather new topic with very few results known at the moment. Our method consists in studying a recurrence formula for these maps and modeling it by a random walk, forgetting completely about the combinatorics of the model.
This is a work in progress with Andrew Elvey-Price, Wenjie Fang and Michael Wallner.
- Adeline Pierrot (LISN, Paris Saclay)
Agrégation de classements: méthodes à base de graphes et utilisation en bioinformatique
Le problème de l'agrégation de classements est le suivant : on dispose en entrée d'un ensemble d'éléments et d'un ensemble de classements de ces éléments, et on veut en sortie un unique classement, qui reflète au mieux l'ensemble des classements pris en entrée. Les applications sont multiples, notamment en bioinformatique, et les techniques de résolution sont nombreuses et ont chacune leurs avantages et leurs inconvénients. Dans cet exposé, nous présenterons des méthodes de résolution à base de graphes ayant fait l'objet de travaux récents dans l'équipe de bioinformatique du LISN.
- Thomas Dreyfus (IMB, Dijon)
Marches dans le quart de plan et holonomie
Prenons une marche dans le quart de plan à petits pas. On peut associer à cette dernière une série génératrice dont la nature (algébrique, holonome, différentiellement algébrique) donne un certain nombre d'informations sur la marche. Dans cet exposé, basé sur l'article "Enumeration of weighted quadrant walks: criteria for algebraicity and D-finiteness” (arXiv:2409.12806) écrit avec Andrew Elvey Price et Kilian Raschel, nous montrons quelles sont les marches qui sont holonomes, y compris lorsqu'on s'autorise à considérer des marches dépendant de paramètres. Pour ce faire, nous introduisons une approche unifiée basée sur la théorie des fonctions elliptiques, qui nous permet d'avoir une preuve commune de la caractérisation de l'algébricité et de l'holonomie des fonctions génératrices.
