2023 – 2024

28 septembre 2023 

• Valentin Bonzom (LIGM, Université Gustave Eiffel),
  Propriétés d’invariance des b-poids pour les cartes déformées de Chapuy et Dołęga.
  Transparents.

Les cartes combinatoires sont des collages de polygones formant des surfaces de genre arbitraire et orientables ou non. On s'intéressera ici à des modèles de cartes, orientables ou non, introduits par Chapuy and Dołęga. Les cartes y sont pondérées par des b-poids, qui sont des polynômes en une variable b, déterminés récursivement par élimination des arêtes à partir de la racine. Ces modèles sont motivés par le lien avec la combinatoire algébrique, au sens où leurs séries génératrices se développent naturellement sur les polynômes de Jack pour la variable alpha=1+b. Néanmoins, la définition des b-poids les rend délicats à manipuler. Nous prouverons des propriétés d'invariance de la moyenne des b-poids qui sont bien connues pour les cartes orientables mais non-triviales ici. Ce sont des résultats à paraître avec Victor Nador (LaBRI - LIPN).

• Cédric Boutillier (LPSM, Sorbonne Université)
  Limites de tableaux de Young aléatoires : une approche déterminantale.
  Transparents.

Nous présentons des résultats pour la limite d'échelle et la limite locale de grands tableaux de Young standards uniformes dont la forme (renormalisée) λ0 est fixée. Le point de départ est l'analyse asymptotique d'un processus déterminantal étudié par Gorin et Rahman, qui permet en particulier :
- de calculer la surface limite pour la limite d'échelle à partir d'une équation polynomiale dépendant de λ0;  
- de décrire la limite locale de ces grands tableaux de Young par une famille de tableaux de Young infinis, construits à partir du processus du collier de perles.
Collaboration avec Jacopo Borga, Valentin Féray et Pierre-Loïc Méliot.

7 décembre 2023 

• • Mireille Bousquet-Mélou (LaBRI, Université de Bordeaux)
    Computer algebra in my combinatorics life.

Transparents.

Many of my papers would just not exist without computer algebra. I will describe how CA has become an essential tool in my research in enumerative combinatorics. The point of view will be that of a (sometimes naive) user, not of an expert. Many examples and questions will be taken from a joint paper with Michael Wallner dealing with the enumeration of king walks avoiding a quadrant (arXiv 2021, to appear). My hope is that some of the questions that I will raise will have an immediate answer ("yes, this is done") and/or that some people in the audience will find a question interesting enough to take it back home.

• • Tony Guttmann (University of Melbourne)
    Self-avoiding walks in a square and the gerrymander sequence.

Transparents.

We give an improved algorithm for the enumeration of self-avoiding walks and polygons within an N×N square as well as SAWs crossing a square. We present some proofs of the expected asymptotic behaviour as the size N  of the square grows, and then show how one can numerically estimate the parameters in the asymptotic expression. We then show how the improved algorithm can be adapted to count gerrymander sequences (OEIS A348456), and prove that the asymptotics of the gerrymander sequence is similar to that of SAWs crossing a square. This work has been done in collaboration with Iwan Jensen, and in part with Aleks Owczarek.

• • Arvind Ayyer (Indian Institute of Science, Bangalore)
    Computer algebra for the study of two-dimensional exclusion processes.

Transparents.

We define a new disordered asymmetric simple exclusion process (ASEP) with two species of particles, first-class and second-class, on a two-dimensional toroidal lattice. The dynamics is controlled by first-class particles, which only move horizontally, with forward and backward hopping rates $p_i$ and $q_i$ respectively if the particle is on row $i$. The motion of second-class particles depends on the relative position of these with respect to the first-class ones, and can be both horizontal and vertical.

In the first part of my talk, I will illustrate how we used computer algebra software, specifically Mathematica and SageMath, to understand the stationary distribution of this process. We computed the partition function, as well as densities and currents of all particles in the steady state. We observed a novel mechanism we call the Scott Russell phenomenon: the current of second class particles in the vertical direction is the same as that of first-class particles in the horizontal direction. In the second part of my talk, I will show how we simulated the process and realized that the Scott Russell phenomenon also holds out of equilibrium.

This is partly joint work with Ph. Nadeau (European Journal of Combinatorics, 2022).

• • Dan Romik (University of California, Davis)
    A new proof of Viazovska’s modular form inequalities for sphere packing in dimension 8.

Transparents.

Maryna Viazovska in 2016 found a remarkable application of the theory of modular forms to a fundamental problem in geometry, obtaining a solution to the sphere packing problem in dimension 8 through an explicit construction of a so-called "magic function" that she defined in terms of classical functions, the Eisenstein series and Jacobi thetanull functions. The same method also led shortly afterwards to the solution of the sphere packing in dimension 24 by her and several collaborators. One component of Viazovska's proof consisted of proving a pair of inequalities satisfied by the modular forms she constructed. Viazovska gave a proof of these inequalities that relied in an essential way on computer calculations. In this talk I will present a new proof of Viazovska's inequalities that uses only elementary arguments that can be easily checked by a human.

8 février 2024 

• Mylène Maida (Université Lille 1)
  Quelques résultats d’universalité pour des mots en des permutations aléatoires

Choisissons uniformément au hasard une permutation de N objets et intéressons-nous à des observables comme la longueur de la plus longue sous-suite croissante, le nombre de descentes, le nombre de cycles d'une taille donnée etc. Le comportement asymptotique de ces observables quand N devient très grand est bien compris. En particulier, il est facile de montrer que la loi jointe des petits cycles est asymptotiquement poissonienne. Si on considère maintenant non plus une permutation mais un mot en plusieurs permutations uniformes indépendantes, on sait, par des travausxde Nica, Magee, Puder etc, que le comportement asymptotique des petits cycles dépend de la structure algébrique du mot considéré et comment il en dépend. Au delà du cas uniforme,  il existe bien d'autres façons intéressantes et/ou naturelles de choisir une permutation  au hasard (loi d'Ewens, de Mallows...). Dans cet exposé, je présenterai des travaux en commun avec Slim Kammoun (ENS Lyon) dans lesquels nous avons essayé de comprendre à quelles conditions (sur les lois des permutations et la structure du mot) les petits cycles du mot en les permutations gardent un comportement asymptotique similaire au cas uniforme.

• Carla Groenland (TU Delft)
  List colouring trees in logspace and new parameterized complexity classes

 A List Colouring instance consists of a graph and for each vertex v in the graph, a list L(v) of colours that it may be coloured with. I will explain some ideas behind our algorithm that decides whether an n-vertex tree admits a list colouring using O(log n) bits on the work tape. No knowledge of parameterized complexity or graph width measures is expected, but I will also advertise new complexity classes (XNLP, XALP, XSLP) that can be defined using List Colouring (parameterized by pathwidth, treewidth, treedepth respectively).

This talk is primarily based on joint work with Hans Bodlaender and Hugo Jacob.

• • Carola Doerr (LIP 6)

Randomized Search Heuristics, their working principles, and the role of theory

Randomized search heuristics form a widely applied class of black-box optimization techniques, designed with the hope to produce high-quality solutions for a great variety of problems and without requiring any problem-specific knowledge. Many different types of randomized search heuristics exist. After discussing their main working principles, we will describe the state of the art in analyzing randomized search heuristics by theoretical means. We will highlight a few examples that demonstrate how these analyses have influenced the design of new algorithmic ideas. To stimulate a discussion with the audience of this seminar, we will  then summarize where the current challenges are.

• • Sanjay Ramassamy (IPhT)

Integrable dynamics on polygons and the dimer integrable system

On the one hand, several discrete-time dynamical systems on spaces of polygons have been shown in the last twenty years to be integrable. On the other hand, Goncharov and Kenyon introduced ten years ago an integrable system associated with the dimer model on bipartite graphs on the torus. Building upon the notion of triple crossing diagram maps (introduced in recent works of Affolter, Glick, Pylyavskyy and myself), I will describe a framework which encompasses both the geometric dynamics on polygons and the dimer integrable system. This framework makes it possible in particular to identify the conserved quantities of both systems. I will illustrate this paradigm on the example of the pentagram map.

This talk is based on joint works with Niklas Affolter (TU Berlin), Terrence George (UCLA), Max Glick (Google) and Pavlo Pylyavskyy (University of Minnesota).

4 avril 2024 

• Lucas Gerin (CMAP, Ecole Polytechnique),
  Plus longue sous-suite croissante dans une multi-permutation

Le problème d'Ulam (ou Ulam-Hammersley, ou Ulam-Hammersley-Versik-Kerov, ou...) consiste à étudier la longueur de la plus longue sous-suite croissante dans une permutation aléatoire uniforme. Apparu dans les années 60, ce problème a été souvent revisité en mélangeant combinatoire algébrique, calcul des variations, matrices aléatoires, processus aléatoires,... Le but de cet exposé est de rappeler le problème historique et de présenter l'approche "processus" pour le problème d'Ulam sur des k-multipermutations : il s'agit de mots dans lesquels chaque lettre parmi 1,...,n apparaît exactement k fois.
Référence : L.Gerin. The Ulam-Hammersley problem for multiset permutations (preprint, 2023).

• Nathalie Aubrun (LISN),
  Jeux de tuiles robustes et problème du domino
  

Transparents.

L'un des problèmes les plus fondamentaux en théorie du pavage est le problème du domino : étant donné un ensemble de tuiles, peut-on décider s'il existe un moyen de paver le plan? Depuis les années 60 on sait que ce problème est indécidable en général y compris en se restreignant aux tuiles de Wang, qui sont des tuiles carrées unitaires avec des couleurs sur leurs bords et que l'on peut assembler à condition qu'elles partagent la même couleur sur leur bord commun. Dans cet exposé je présenterai une notion de robustesse pour des jeux de tuiles de Wang : plusieurs jeux de tuiles célèbres de la littérature possèdent cette propriété, et satisfont donc un certain invariant de manière prouvable, et le problème du domino devient décidable pour les jeux de tuiles robustes.
Il s’agit d’un travail en collaboration avec Manon Blanc et Olivier Bournez.

• Alin Bostan (INRIA Saclay),
  How to decide if a D-finite power series is algebraic?
  

Transparents.

A power series is said to be D-finite ("differentially finite”) if it satisfies a linear differential equation with polynomial coefficients. D-finite power series are ubiquitous in combinatorics, as well as in number theory and mathematical physics. In a seminal 1980 article, Richard Stanley asked whether it is possible to decide if a given D-finite power series is algebraic or transcendental.  There are several very useful sufficient criteria for transcendence, but none also provides a sufficient condition. One of them is a powerful criterion due to Philippe Flajolet, based on asymptotics of coefficients. Characterizing the algebraicity of a D-finite power series is a highly non-trivial task even if the sequence of its coefficients satisfies a recurrence of order one: this question was completely settled only in 2023 by Florian Fürnsinn and Sergey Yurkevich, building on important articles by Gilles Christol (1986) and by Frits Beukers and Gert Heckman (1989). In this talk, I will present answers to Stanley’s question and illustrate them through several examples coming from combinatorics and number theory.

6 juin 2024 

• Gilles Schaeffer (LIX, Polytechnique)
  From catalytic to algebraic decompositions, bijectively

A celebrated result of Bousquet-Mélou and Jehanne states that under reasonable combinatorial hypotheses the solutions of polynomial equations with one catalytic variable are algebraic series. We give a combinatorial derivation of this result in the case of order one catalytic equations (those involving only one univariate unknown series), in the form of a recipe to derive systematically an algebraic decomposition or a bijection with a simply generated family of trees from an order one catalytic decomposition. 

Joint work with Enrica Duchi.

• Aline Parreau (LIRIS, Université Lyon 1)
  Complexité algorithmique du jeu de domination Maker-Breaker sur les graphes

Dans cet exposé, nous expliquerons à travers l'exemple du jeu de domination Maker-Breaker dans les graphes comment être sûr de pouvoir construire une structure donnée face à un adversaire malveillant. Dans le jeu de domination dans les graphes, à chaque tour, Dominator choisit un sommet du graphe puis Staller lui interdit un sommet. A la fin, Dominator gagne si elle a obtenu un ensemble dominant avec ses sommets: c'est-à-dire si chaque sommet du graphe est à distance au plus 1 d'un sommet de Dominator.

Alors que les problèmes classiques de graphes sont très souvent dans la classe NP, savoir si Dominator peut gagner à tous les coups est un problème PSPACE-complet. Cela est en particulier dû au fait que décrire une stratégie pour l'un des joueurs ne peut se faire en temps polynomial en général. Nous verrons dans cet exposé des stratégies structurelles pour Dominator qui sont suffisantes pour certaines classes de graphes comme les graphes d'intervalles, les graphes planaires extérieures ou les graphes réguliers. Cela permet en particulier d'améliorer la complexité du problème dans ces classes de graphes : ainsi les graphes réguliers peuvent toujours être dominés par Dominator, déterminer qui gagne pour un graphe planaire extérieur est polynomial. Pour les graphes d'intervalles, nous obtenons que ce problème est dans NP en le ramenant à la recherche d'une structure particulière dans le graphe mais ne savons pas si cette recherche peut se faire en temps polynomial...

• Baptiste Rognerud (IMJ-PRG)
  Un ordre partiel d’origine algébrique sur les tableaux de permutation

Les treillis de Tamari sont des ordres partiels particulièrement bien étudiés, qui apparaissent dans de nombreux domaines des mathématiques.En théorie des représentations ils apparaissent, par exemple, comme ensembles de modules basculants d'une certaine algèbre. Dans cet exposé nous allons brièvement introduire une famille de modules qui généralise les modules basculants. Ces modules sont en réalité très anciens, ils remontent essentiellement à Schur, mais de façon curieuse aucun résultat de classification n'a été obtenu avant nos travaux. Nous allons voir que dans un cas simple, cette classification fait intervenir de la combinatoire très sympathique de remplissages de diagrammes.
Il sera ensuite très naturel d'introduire une relation d'ordre sur ces objets et nous verrons que celle-ci généralise la relation d'ordre de Tamari. Informellement c'est un "ralentissement" de la rotation des arbres binaires. Dans la seconde partie de l'exposé, nous verrons que cette relation d'ordre possède d'excellentes propriétés : essentiellement toutes les propriétés de l'ordre de Tamari.
C'est un travail en commun avec Crawley-Boevey, Ma et Sauter et plus récemment avec Corteel et Jang.