2017-2018
Lundi 9 juillet : Stéphane Dartois (Univ. Melbourne, Australie)
Titre : Combinatorics of joint moments of marginals of random density matrices
Résumé : In this presentation I will describe the different combinatorial objects appearing in the description of moments of products of different marginals of random matrices. In the general case these objects can be seen as (unicellular) combinatorial maps carrying some additional structures. The study of their combinatorics allows one to study different regimes for the parameters used to define the different marginals and to give freeness results (in the sense of free probability) for some of these regimes. This is a joint work with Luca Lionni and Ion Nechita.
Jeudi 5 juillet : Laura Ciobanu (Université Heriot-Watt d'Édimbourg, Écosse, Royaume-Uni) http://www.macs.hw.ac.uk/~lc45/
Titre : Combinatorial hypermaps in 2 and 3 dimensions and subgroup growth
Résumé : In this talk I will present a way of counting 2 and 3 dimensional rooted or unrooted orientable hypermaps with respect to the number of their darts by using species theory, and make the link to counting free subgroups of finite index in free products of finite groups. This is joint work with Alex Kolpakov.
Vendredi 29 juin : Luis Maximiliano Fredes Carrasco
Titre : Invariant measures of discrete interacting particle systems: algebraic aspects.
Résumé :
Particle systems are a set of particles embedded in a graph, evolving randomly according to some politics.
Among them we find the TASEP, the Contact process, the voter models and the zero range process.
These are a particular type of continuous time Markov process; typically, the Markovian evolution is driven by some translation invariant local dynamics with bounded width dependence, encoded by a rate matrix T, meaning that the evolution of the particle at a given position depends only on the particles in a finite neighborhood of it and this evolution rule is invariant under translation.
We consider a continuous time particle system on a graph L being either Z, Z_n, a segment {1,…, n}, or Z^d, with state space Ek={0,…,k-1} for some k belonging to {infinity, 2, 3, …}.
These are standard settings, satisfied by many studied particle systems.
We provide some sufficient and/or necessary conditions on the matrix T, so that this Markov process admits some simple invariant distribution, as a product measure, as the distribution of a Markov process indexed by Z or {1,…, n} (if L=Z or {1,…,n}), or as a Gibbs measure (if L=Z_n).
We will show how these results give efficient ways to find Markovian invariant distributions for a given rate matrix or to prove that none exists.
We will also present some applications on well known models and mild modifications of them.
Vendredi 22 juin : Michael Wallner
Titre : Periodic Pólya urns and an application to Young tableaux
Résumé :
Pólya urns are urns where at each unit of time a ball is drawn uniformly at random and is replaced by some other balls according to its colour.
We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time mod p.
Our key tool are generating functions, which encode all possible urn compositions after a certain number of steps.
The evolution of the urn is then translated into a system of differential equations and we prove that the moment generating functions are D-finite.
From these we derive asymptotic forms of the moments.
When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions.
Furthermore, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux.
This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.
Vendredi 8 juin : Élise Vandomme (Université du Québec À Montréal (UQÀM), Canada)
Title: Critical exponent of balanced words
Abstract :
Over a binary alphabet it is well-known that the aperiodic balanced words are exactly the Sturmian words.
The repetitions in Sturmian words are well-understood.
In particular, there is a formula for the critical exponent (supremum of exponents ⚠ $e$ such that ⚠ $x^e$ is a factor for some word ⚠ $x$) of a Sturmian word.
It is known that the Fibonacci word has the least critical exponent over all Sturmian words and this value is ⚠ $(5+\sqrt{5})/2$.
However, little is known about the critical exponents of balanced words over larger alphabets.
We show that the least critical exponent among ternary balanced words is ⚠ $2+\sqrt{2}/2$ and we construct a balanced word over a four-letter alphabet with critical exponent ⚠ $(5+\sqrt{5})/4$.
This is joint work with N. Rampersad and J. Shallit.
Vendredi 1er juin : Xavier Viennot
Titre : Un nouveau regard sur la correspondance RSK et le jeu de taquin
Résumé : La correspondance RS (Robinson-Schensted) est une bijection entre les permutations et les paires de tableaux de Young de même forme. Il y a une trentaine d'années, S. Fomin en a donné une description récursive avec des règles locales de « croissances de diagrammes de Ferrers » ("growth diagrams"), ainsi que pour le célèbre « jeu de taquin » inventé par M.P. Schützenberger. Ces règles locales sont à la base de nombreux articles en combinatoire algébrique. Cet exposé est un plaidoyer pour changer ces deux systèmes de règles locales (agissant sur les sommets entourant une cellule élémentaire) par des règles locales plus simples agissant sur les arêtes entourant la dite cellule. En introduisant le produit « RSK » de deux mots, nous étendons ce point de vue à la correspondance RSK (Robinson-Schensted-Knuth), ainsi que sa duale, entre matrices à coefficients entiers et paires de tableaux de Young semi-standards de même forme.
Vendredi 25 mai : Olya Mandelshtam (université Brown, Providence, États-Unis)
Titre : Combinatorics of the ASEP on a ring
Résumé :
The m-species asymmetric simple exclusion process (m-ASEP) on a ring is a Markov chain on a ring with n sites with each site either vacant or occupied by one of m classes of particles, and whose dynamics are dictated by parameter q: particles can hop right at rate 1 or left at rate q.
At q=0, the stationary probabilities of the states of the m-ASEP can be described by multiline queues of Ferarri and Martin.
For the 2-ASEP, we show a new combinatorial description of these probabilities in terms of certain cylindric tableaux which are in bijection with the multiline queues.
We then extend this result for general q, which furthermore gives a combinatorial formula for some classes of Macdonald polynomials.
This talk is based on ongoing work with Sylvie Corteel (Université Paris-Diderot) and Lauren Williams (Berkeley).
Vendredi 18 mai : Mélodie Lapointe (Université du Québec À Montréal (UQÀM), Canada)
Titre : Combien d’orbites a un échange d'intervalles discrets ?
Résumé : Les échanges d'intervalles discrets ont été introduits par Ferenczi et Zamboni pour décrire un ensemble de mots, les mots primitifs ordonnés. Les échanges d'intervalles discrets sont engendrés par une composition. On peut alors se demander quel est le nombre d'orbites d'un échange d'intervalles discrets à partir de sa composition ? De tels critères sont connus pour les compositions ayant 2 et 3 composantes. Dans cet exposé, un algorithme répondant à cette question pour toutes les compositions sera présenté, ainsi que des applications de celui-ci.
~~~~~
Vendredi 18 mai : Nadia Lafrenière (Université du Québec À Montréal (UQÀM), Canada)
Titre : Propriétés spectrales des opérateurs de mélange symétrisés
Résumé : Je vais parler d'un projet en cours avec Franco Saliola et Stéphanie Schanck, dans lequel nous cherchons les valeurs propres de certains opérateurs introduits par Victor Reiner, Franco Saliola et Volkmar Welker en 2014. Ces opérateurs peuvent être interprétés comme des mélanges de cartes à jouer. Il est naturel de se demander combien de répétitions d'un même opérateur sont nécessaires pour qu'un paquet de cartes soit bien mélangé. Parmi les opérateurs étudiés, nous avons la réponse pour un seul des mélanges, le mélange doublement aléatoire. Pour les autres, la réponse pourrait passer par les valeurs propres, et c'est pourquoi nous sommes à leur recherche.
Vendredi 27 avril : Élie de Panafieu (équipe Mad Men, Bell Labs France, Nokia ; membre associé au Laboratory of Information, Networking and Communication Sciences) https://www.lincs.fr/people/elie-de-panafieu/
Titre : Marches à une dimension non déterministes
Résumé :
En informatique, la notion de « non-déterminisme » ne signifie pas « aléatoire » (malgré ce que le nom pourrait le laisser entendre), mais désigne les processus de calcul qui, à chaque étape, peuvent se dupliquer pour explorer plusieurs possibilités en parallèle.
Nous proposons une extension de cette notions aux marches à une dimension.
On place sur chaque entier de 0 à n-1 de l'axe des abscisses un ensemble aléatoire de pas disponibles (un pas étant un entier relatif).
Puis on considère toutes les marches commençant à l'origine qui, à chaque étape, se déplacent sur l'axe des ordonnées en utilisant un des pas disponibles, et avancent d'une unité sur l'axe des abscisses.
Nous traiterons dans cet exposé les deux questions suivantes.
Quelle est la probabilité qu'au moins une de ces marches termine en ordonnée 0 ?
Quelle est la probabilité qu'au moins une des ces marches reste dans le demi-plan des ordonnées positive et termine en 0 ?
Il s'agit d'un travail en cours avec Lamine Lamali, motivé par l'étude des performances des réseaux utilisant des protocoles d'encapsulation et de décapsulation de paquets.
Nos preuves utilisent des techniques de séries génératrices développées notamment pour l'étude des marches
sur la ligne et dans le plan.
~~~~~
Vendredi 27 avril : Valentin Bonzom (équipe CALIN du LIPN, Université Paris 13) http://lipn.univ-paris13.fr/~bonzom/
Titre : Les triangulations de dimension d>2 qui maximisent le nombre de simplexes de dimension d-2
Résumé : Trouver des familles de triangulations en dimension d>2 pour lesquelles l'énumération serait à la fois faisable et intéressante est une problème très difficile. Les triangulations dites colorées, introduites en topologie depuis une trentaine d'années mais considérées du point de vue énumératif depuis peu, offrent un cadre dans lequel on peut classifier et énumérer des triangulations. De plus, il est possible de tester les classes d'universalité en étudiant des familles dont les briques de construction sont contraintes, par exemple en n'utilisant que des octaèdres ou que des bipyramides en 3D. La classification repose sur une généralisation combinatoire de la formule d'Euler pour le genre, consistant à borner le nombre de simplexes de dimension d-2 linéairement en le nombre de simplexes. En 3D par exemple, on borne le nombre d'arêtes en fonction du nombre de tétraèdres. Ces bornes dépendent en fait des briques élémentaires utilisées. On peut néanmoins montrer qu'en 3D les triangulations qui maximisent le nombre d'arêtes sont toujours en bijection avec des arbres. En 4D (et même en toutes dimensions paires), en utilisant plusieurs briques de construction et variables de comptage associées, on trouve pour les triangulations qui maximisent le nombre de triangles un régime dominé par les arbres, un autre par les cartes planaires et une transition de phase entre arbres et cartes planaires.
Vendredi 6 avril : Avelio Sepúlveda Donoso (université Lyon 1) http://math.univ-lyon1.fr/homes-www/sepulveda/
Titre : Densité d'un cluster de la soupe de boucles critique
Résumé :
Travaux en commun avec Juhan Aru et Titus Lupu.
La soupe des boucles de paramètre 1 est un objet probabiliste gardant l'information des boucles effacées lorsqu'on construit un arbre couvrant uniforme en utilisant l'algorithme de Wilson.
Pour obtenir des soupes de boucles de paramètre plus petit, il suffit d'en oublier quelques-unes.
Dans cet exposé on va s'intéresser à la densité de clusters associé à une soupe de boucles d'un certain paramètre.
Un cluster est une composante connexe du graphe induit par les arêtes des boucles.
La densité d'un cluster de la soupe de boucles dépend du paramètre : quand il est plus grand que ⚠ $1/2$ (y compris le cas de l'algorithme de Wilson), la densité d'un cluster macroscopique est près de 1 ; et quand le paramètre est inférieur ou égal à ⚠ $1/2$, la densité est près de 0.
L'objectif de l'exposé sera de discuter de la vitesse à laquelle la densité d'un cluster macroscopique de la soupe de boucle de paramètre ⚠ $1/2$ converge vers 0.
Le résultat est une conséquence des liens récemment établis entre la soupe de boucles et le champ libre Gaussien, et l'introduction d'une approximation semi-continue de la soupe de boucles.
~~~~~
Vendredi 6 avril : Robert Cori
Titre : Un groupe diédral opérant sur les mots de Dyck.
Résumé :
Je reviendrai sur deux involutions opérant sur les ensembles des mots de Dyck de même longueur et vous raconterai les résultats obtenus pour le groupe qu’elles engendrent.
Je tenterai de justifier mon intérêt pour ces involutions en faisant référence à notre travail en commun avec Y. Le Borgne concernant le rang des configurations du modèle du tas de sable pour le graphe complet.
Enfin il sera question de conjectures portant sur une généralisation de ces opérations pour les mots d’un d’alphabet à deux lettres.
Travail en commun avec M. Barnabei, F. Bonetti, N. Castronuovo puis avec S. Labbé.
Vendredi 30 mars : Éric Balandraud
Titre : Combinatoire additive et Combinatorial Nullstellensatz
Résumé : Dans cet exposé, je voudrais donner une double introduction : une introduction à la combinatoire additive, issue de la théorie additive des nombres et notamment les théorèmes d'addition d'ensembles (Cauchy-Davenport, Dias da Silva-Hamidoune) et une introduction au Combinatorial Nullstellensatz. Le Combinatorial Nullstellensatz est un théorème généralisant en plusieurs variables le fait qu'un polynôme (univarié) de degré d ne puisse accepter plus de d racines. Développé dans les années 90, ce théorème s'est révélé très pratique dans des domaines extrêmement différents, théorie des graphes, géométrie discrète, combinatoire additive et théorie des nombres.
Vendredi 9 mars : Henri Derycke
Titre :
Automate reconnaissant dans le modèle du tas de sable les configurations récurrentes gauches sur une bande de hauteur ⚠ $H$.
Résumé :
Le modèle du tas de sable se définit bien pour tout graphe fini.
Jarai et Lyons ont approximé le comportement sur la bande bi-infinie de hauteur ⚠ $H$ dans ⚠ $\mathbb{Z}^2$ par une suite de rectangles de hauteur ⚠ $H$ de plus en plus large.
Cela les conduit notamment à la notion de configuration récurrente éboulable de la gauche.
On s'intéresse alors à des automates reconnaissant colonne par colonne ces configurations.
Jarai et Lyons en donnent un automate explicite pour la hauteur ⚠ $H=2$ et ont montré qu'il existe un automate pour tout ⚠ $H$ avec au plus ⚠ $(2^H)^{2^H}$ états.
Dans sa thèse, Gamlin conjecture, en s'appuyant sur des simplifications, qu'on peut réduire le nombre d'états en ⚠ $\alpha^H$.
En s'appuyant sur une bijection entre les récurrentes et les arbres couvrants et sur une étude combinatoire, je proposerai une borne probablement grossière sur le nombre d'états, en ⚠ $\alpha^{H\log H}$.
Les algorithmes liés à ces bornes permettent de produire les automates pour la hauteur ⚠ $H=3$ et ⚠ $H=4$.
Dans cette construction, l'automate contient au moins ⚠ $\beta^{H}$ états car on isole un sous-ensemble de ces états en bijection avec les permutations séparables (celles évitant les motifs 3142 et 2413).
Ce travail en cours est aussi en lien et motivé par l'analyse également en cours de simulations impliquant le modèle du tas de sable.
~~~~~
Vendredi 9 mars : José Manuel Rodriguez Caballero
Titre : Un corps à un nombre négatif d’éléments est-il possible ?
Résumé : On commence par l’heuristique du « corps à un élément » (J. Tits), ainsi que ses « extensions » liées aux racines de l'unité (A. Weil, K. Iwasawa). On explique brièvement la formalisation de cette idée (théorie de topos et géométrie tropicale) développée par A. Connes, C. Consani et M. Marcolli dans le cadre de la géométrie non-commutative. À titre d’exemple du lien parmi la géométrie en caractéristique p > 1 (corps finis), la géométrie en caractéristique 0 (nombres complexes) et la géométrie en caractéristique 1 (semi-corps tropical), on énonce quelques résultats de R. Bacher et C. Reutenauer, de C. Kassel et C. Reutenauer, de M. Reineke, de S. Mozgovoy et M. Reineke, et de T. Hausel, E. Letellier et F. Rodriguez-Villegas, concernant des q-analogues ayant des interprétations combinatoires classiques. Finalement, on montre que, lorsque l’on substitue le nombre q d’éléments d'un corps fini par -q, dans un q-analogue étudié par C. Kassel et C. Reutenauer, on obtient une suite de polynômes qui détermine les hypoténuses des triplets pythagoriciens primitifs. Ce résultat motive la recherche d’une formalisation de la géométrie et la combinatoire d’un objet dont son comportement doit correspondre à un corps hypothétique à « un nombre négatif d’éléments » au sens de J. Tits.
Vendredi 2 mars : Éric Fusy (LIX, École Polytechnique) http://www.lix.polytechnique.fr/Labo/Eric.Fusy/
Titre : Diagrammes de Voronoï dans les arbres et cartes aléatoires d'excès fini.
Résumé :
Pour Gn un graphe aléatoire (selon un certain modèle) à n sommets, et pour k sommets (k≥2 étant fixé) de Gn pris au hasard, on considère la partition associée en k cellules de Voronoï C1,...,Ck et le vecteur Vn(k) = ⚠ $\frac{|C_1|}{n},...,\frac{|C_k|}{n}$ donnant la répartition des masses des cellules.
Le modèle est dit asymptotiquement uniforme pour Voronoï si la distribution limite de Vn(k) est la loi uniforme sur le simplexe {x1+...+xk=1, xi≥0}.
Plusieurs modèles d'aspects très différents possèdent ou semblent posséder cette propriété, notamment le graphe complet Kn avec des longueurs d'arêtes suivant des lois exponentielles, et plus récemment il a été conjecturé par Guillaume Chapuy que c'est le cas pour les cartes aléatoires de genre g (avec la preuve que certains moments joints sont bien en adéquation avec la loi uniforme), ce qui a été récemment prouvé par Emmanuel Guitter pour le cas {g=0, k=2}.
Nous montrerons ici que la propriété d'uniformité est vraie pour les arbres aléatoires et plus généralement pour les cartes unicellulaires de genre g.
La preuve repose sur une bijection, tout d'abord formulée pour les arbres plans avec k coins marqués, qui envoie (modulo des termes d'erreur o(1)) le vecteur de masses des cellules de Voronoï vers le vecteur donnant les longueurs d'intervalles pour la partition du contour selon les coins marqués.
Cette bijection admet une extension naturelle aux cartes de genre et excès fixés, qui permet d'obtenir la propriété d'uniformité pour les cartes unicellulaires de genre g.
Travaux en commun avec Louigi Addario-Berry, Omer Angel, Guillaume Chapuy et Christina Goldschmidt.
Vendredi 16 février : Alessandro Iraci (Université de Pise, Italie)
Titre : Parallelogram Polyominoes and the Delta Conjecture
Résumé : The Delta Conjecture is an important open problem in algebraic combinatorics. It gives a combinatorial interpretation for certain instances of the Delta operator, which is a linear operator on the space of symmetric functions that acts diagonally on the basis of Macdonald polynomials. The Delta Conjecture is stated in terms of parking functions, which are labelled Dyck paths. We give a combinatorial interpretation for some particular instances of the Delta Conjecture in terms of decorated parallelogram polyominoes, showing some recursions and proving the “hh” case using a bijection with some subset of parking functions.
Vendredi 9 février : Michael Wallner http://dmg.tuwien.ac.at/mwallner/
Titre : Asymptotic Enumeration of Compacted Binary Trees with Height Restrictions
Résumé :
When storing rooted trees it is useful to consider compression techniques.
A simple idea is to store isomorphic subtrees only once and mark repeated occurrences with a pointer.
A classical algorithm to establish such a compaction was analyzed by Flajolet, Sipala, and Steyaert.
The resulting structure is called a compacted tree, being in fact no more a tree but a directed acyclic graph.
Our goal is the enumeration of such structures.
Since the enumeration turns out to be extremely difficult, we restrict it to a sub problem by imposing a bound on the so-called right height.
We solve this enumeration problem with the help of generating functions.
Due to the superexponential growth of the counting sequence we use exponential generating function despite the fact that these objects are unlabeled.
We first derive a calculus on exponential generating function capturing their recursive nature.
This leads to a sequence of differential equations for the generating functions (also implying their D-finiteness) for which a singularity analysis is carried out.
This work is based on joint work with Antoine Genitrini, Bernhard Gittenberger, and Manuel Kauers.
Vendredi 2 février : Shigeki Akiyama (Université de Tsukuba, Japon) http://math.tsukuba.ac.jp/~akiyama/
Titre : Mean divisibility of sequences
Résumé :
A sequence ⚠ $(a_n)$ of integers is called divisible, if ⚠ $n \mid m$ implies ⚠ $a_n \mid a_m$.
We consider a weaker terminology; mean divisibility and give non-trivial examples which satisfies the property.
A typical result is
⚠ $\displaystyle{ \frac{\prod_{n=1}^{t} {10n \choose 4n}}{\prod_{n=1}^{t} {5n \choose 2n}} \in \frac{1}{11}{\mathbb Z} }$for all ⚠ $t$.
We explain the underlying idea of the proof, which involves an interesting statistical behavier of an arithmetic function.
Vendredi 26 janvier : Milton Minervino
Titre : Fractales de Rauzy et substitutions d'arbre (2/2)
Résumé : Le but de cet exposé sera de vous apprendre qu'on peut interpréter géométriquement une classe de systèmes dynamiques substitutifs, dits de type Pisot, par des fractales, introduits pour la première fois par G. Rauzy. Si le temps le permet, je montrerai aussi comment construire des arbres qui approximent et remplissent ces fractales. De cette façon on peut relier la dynamique du système substitutif avec un échange d'intervalles.
Vendredi 19 janvier : Jérôme Leroux
Titre : Utilisation des petites solutions dans les systèmes à compteurs.
Résumé : Le théorème des petites solutions montre que tout système linéaire homogène à coefficients entiers admet des « petites » solutions. Ce théorème permet par exemple de montrer que la programmation linéaire est décidable dans NP. Je rappellerai dans cette présentation le théorème des petites solutions de Loïc Pottier et donnerai un exemple d’utilisation en vérification formelle pour décider le caractère borné d’un réseau de Petri dans EXPSPACE (théorème de Rackoff).
Vendredi 12 janvier : Milton Minervino
Titre : Fractales de Rauzy et substitutions d'arbre (1/2)
Résumé : Le but de cet exposé sera de vous apprendre qu'on peut interpréter géométriquement une classe de systèmes dynamiques substitutifs, dits de type Pisot, par des fractales, introduits pour la première fois par G. Rauzy. Si le temps le permet, je montrerai aussi comment construire des arbres qui approximent et remplissent ces fractales. De cette façon on peut relier la dynamique du système substitutif avec un échange d'intervalles.
Vendredi 22 décembre : Nicolas Bonichon
Titre : A bijection for essentially 4-connected toroidal triangulations
Résumé : Transversal structures (also known as regular edge labelings) are combinatorial structures defined over 4-connected plane triangulations with quadrangular outer-face. They have been intensively studied and used for many applications (drawing algorithm, random generation, enumeration...). In this paper we introduce and study a generalization of these objects for the toroidal case. Contrary to what happens in the plane, the set of toroidal transversal structures of a given toroidal triangulation is partitioned into several distributive lattices. We exhibit a subset of toroidal transversal structures, called balanced, and show that it forms a single distributive lattice. Then, using the minimal element of the lattice, we are able to enumerate bijectively essentially 4-connected toroidal triangulations.
Vendredi 15 décembre : Manon Stipulanti (Université de Liège, Belgique) http://www.math.ulg.ac.be/stipulanti/
Titre : Une extension des triangles de Pascal et de Sierpinski aux mots finis
Résumé :
Le coefficient binomial binomial(u,v) de deux mots u et v est défini comme le nombre de fois que le mot v apparaît comme sous-suite du mot u.
Par exemple, binomial(abbab,ab)=4.
Il étend de manière naturelle le coefficient binomial de deux entiers.
Ce concept a été largement étudié depuis plus d'une trentaine d'années (consulter, par exemple, les travaux de Simon et Sakarovitch).
Dans cet exposé, je parlerai des recherches effectuées dans le cadre de ma thèse : j'exposerai les grandes idées qui ont mené à une extension des triangles de Pascal et de Sierpinski à ces coefficients.
Je donnerai également un aperçu des résultats obtenus jusqu'ici et liés à ces généralisations.
Il s'agit d'un travail en commun avec Julien Leroy (Université de Liège) et Michel Rigo (Université de Liège).
Vendredi 8 décembre : Irène Marcovici (Institut Élie Cartan de Lorraine, Nancy) http://www.iecl.univ-lorraine.fr/~Irene.Marcovici/
Titre : Automates cellulaires probabilistes à mémoire deux : une riche zoologie
Résumé :
Je présenterai un famille d'automates cellulaires probabilistes à mémoire deux, dont l'introduction est motivée par l'étude de modèles issus de la physique statistique (modèle à 8 sommets, TASEP...).
Nous donnons les conditions que doivent satisfaire les probabilités de transition pour que l'ACP ait une distribution invariante de forme produit, et montrons que dans ce cas, la dynamique est ergodique.
L'étude des propriétés de réversibilité multi-directionnelle de ces ACP permet alors d'exhiber d'autres valeurs des paramètres pour lesquelles la distribution invariante peut être calculée explicitement, bien qu'elle n’ait pas une forme simple.
Il s'agit d'un travail en collaboration avec Jérôme Casse.
Vendredi 1er décembre : Ghazal Kachigar
Titre : Processus de Fibonacci sur Z résistants à la localisation
Résumé :
Dans une série d’articles datant de 2015 et de 2016, Holroyd et Liggett ont étudié l’existence de processus de coloration sur le chemin infini Z ayant la propriété de k-dépendance, c’est-à-dire l’indépendance des distributions de probabilités des ensembles de variables aléatoires à distance au moins k les uns des autres.
Ces processus de coloration induisent un processus binaire que nous avons baptisé « processus de Fibonacci » sur Z.
Holroyd et Liggett ont également étudié ce processus de Fibonacci sous l’angle de la 1-dépendance.
Nous avons étudié chez ces processus de Fibonacci une propriété a priori plus faible que la 1-dépendance, en lien avec les algorithmes distribués quantiques, que nous avons appelé la 1-localisabilité.
Cette propriété s’est avérée être distincte de la 1-dépendance mais nous avons démontré qu'un des résultats clés de Holroyd et Liggett, à savoir l’inexistence d’une 3-coloration reste vrai même si l’on exige que celle-ci soit non pas 1-dépendante mais 1-localisable.
De plus, en étudiant la 1-localisabilité, nous avons découvert des liens avec les nombres de Catalan et certaines de leurs propriétés.
Vendredi 24 novembre : Philippe Duchon
Titre : Simulation à mémoire finie de lois de probabilités continues
Résumé :
On s'intéresse ici à la question de savoir quelles lois de probabilités à densité (sur [0,1]) peuvent être simulées en n'utilisant qu'une mémoire bornée.
Assez naturellement, on se ramène à considérer des automates probabilistes qui écrivent le développement (binaire, ou plus généralement, D-aire) d'un réel aléatoire.
Dans ce modèle, on dispose de deux résultats :
Knuth et Yao ont prouvé en 1976 que les seules distribution à densité analytique qui peuvent être simulées, sont en fait à densité polynomiale ;
et Vatan a caractérisé en 2001 les densités polynomiales qui sont simulables.
Je propose une nouvelle preuve du résultat de Vatan, qui a l'avantage d'être constructive (on a un algorithme qui, partant de la densité, construit un automate qui la simule), mais aussi de caractériser les densités simulables parmi celles qui sont seulement polynomiales par morceaux.
Vendredi 10 novembre : Jean-Philippe Labbé (Université libre de Berlin, Allemagne) http://page.mi.fu-berlin.de/labbe/
Titre : Dissections du carré avec des triangles de surfaces presque égales
Résumé :
Le théorème de Monsky de 1970 stipule qu'un carré ne peut pas être découpé en un nombre impair n de triangles ayant la même aire.
La preuve de Monsky ne fournit pas une borne inférieure pour la différence minimale entre les aires des
triangles.
Durant l'exposé, nous explorerons ce problème de minimisation en géométrie.
D'une part, nous donnons une borne inférieure doublement exponentielle à l'aide d'une technique provenant de géométrie semi-algébrique réelle.
D'autre part, nous obtenons une première borne supérieure superpolynomiale pour ce problème, dérivée d'une construction explicite faisant intervenir la suite de Thue-Morse.
Ces travaux ont été faits en collaboration avec Günter Rote et Günter Ziegler.
~~~~~
Vendredi 10 novembre : Michaël Rao (Laboratoire de l'Informatique du Parallélisme, ENS Lyon) https://perso.ens-lyon.fr/michael.rao
Titre : Recherche exhaustive des pentagones convexes pavant le plan.
Résumé : Quand on cherche à caractériser les formes convexes pouvant paver le plan (en s’autorisant les rotations et miroirs), seul le cas des pentagones restait ouvert. De 1918 à 2015, 15 différents types de pentagones pouvant paver le plan ont été découverts. Je présente une recherche exhaustive de tous les pentagones convexes pavant le plan, qui permet de clore cette question. La preuve se sépare en deux parties : la première montre, en utilisant la compacité, qu'on peut se limiter à un ensemble de 371 familles, et la seconde est une recherche exhaustive informatisée, pour chacune des 371 familles, qui ne trouve aucun nouveau type de pentagones que les 15 types connus.
Vendredi 27 octobre : Pierre-Louis Giscard (Université d'York (Angleterre, Royaume-Uni)) https://www-users.cs.york.ac.uk/~plg508/
Titre : Cribles, de la théorie des nombres aux polygones auto-évitants.
Résumé : Dans cet exposé nous présenterons une introduction à l’utilisation de cribles pour l’énumération asymptotique des polygones auto-évitants sur les réseaux régulier du plan. Partant de principes généraux valides pour tous les graphes, nous montrerons que de tels cribles ne peuvent fonctionner que sur les graphes infinis transitifs. Cette conclusion découlera d’un résultat simple que nous prouverons concernant la fraction asymptotique du nombre de chemins multiples d’un cycle simple donné, illustrant également la correspondance profonde entre la combinatoire des randonnées (c’est-à-dire des empilements de cycles simples) et la théorie des nombres. Finalement, nous obtiendrons une équation satisfaite asymptotiquement par la fonction dénombrant les polygones auto-évitants du réseau carré et soulignerons la difficulté qui reste à surmonter. Nous présenterons en outre quelques applications inattendues du crible en théorie des nœuds et même en biologie.
Vendredi 20 octobre : José Manuel Rodriguez Caballero (Laboratoire de combinatoire et d'informatique mathématique de l'UQÀM (Université du Québec à Montréal), Québec, Canada)
Titre : Théorèmes arithmétiques démontrés par Théorie des Langages.
Résumé : On montre une méthode pour démontrer des théorèmes en Théorie Élémentaire des Nombres en utilisant des propriétés des mots de Dyck.
Vendredi 13 octobre : Montserrat Casals-Ruiz (Euskal Herriko Unibertsitatea http://www.ehu.eus/en/en-home (Université du Pays Basque)) http://montsecasals.wixsite.com/montse
Titre : When are right-angled Artin groups similar?
Résumé : Right-angled Artin groups arise naturally in different branches of mathematics and computer science. In this talk we will introduce the class of right-angled Artin groups and discuss when they are algebraically, geometrically and logically similar, or, more formally, when they are commensurable, quasi-isometric and universally equivalent.
Vendredi 6 octobre : Marilena Barnabei (Université de Bologne (Italie)) https://www.unibo.it/sitoweb/marilena.barnabei/en
Titre : Motzkin tunnel polynomials
Résumé :
We define a sequence of polynomials associated with Motzkin paths and explore their properties.
In particular we show that such polynomials satisfy a recurrence relation and present a remarkable symmetry.
We study in detail many different specializations of these polynomials that turn out to be sequences of great interest in combinatorics, such as Schroeder numbers, Fibonacci numbers, q-Catalan polynomials, Narayana polynomials.
~~~~~
Vendredi 6 octobre : Francis Lazarus (Grenoble Images Parole Signal Automatique (GIPSA-Lab) - Grenoble INP) http://www.gipsa-lab.grenoble-inp.fr/page_pro.php?vid=88
Titre : Calcul du nombre géométrique d'intersection d'une courbe
Résumé : Comment reconnaître si une courbe tracée sur une surface peut être déformée continûment en une courbe simple, c'est-à-dire sans croisement ? Plus généralement, comment calculer le nombre minimal de croisements parmi toutes les déformations continues de cette courbe ? Après quelques rappels historiques, je présenterai un point de vue algorithmique sur cette question et montrerai que des techniques élémentaires empruntées à la théorie géométrique des groupes permettent d'y répondre efficacement.
Vendredi 29 septembre : Xavier Viennot http://viennot.org/
Titre : Les maules (2e partie) : m-Tamari et au delà Tamari(v)
Résumé :
Nous reprenons la notion de « maule » introduite dans l’exposé précédent.
Toute partie du réseau carré engendre un maule par un processus dynamique de particules sauteuses.
Le treillis de Tamari défini sur les arbres peut aussi se définir sur les chemins de Dyck.
Ceci permet une extension (pour m entier) donnée par F. Bergeron, appelée m-Tamari, en liaison avec des considérations profondes d’algèbre.
Des conjectures difficiles ont été résolues par M. Bousquet-Mélou et ses coauteurs.
Un problème resté ouvert était de donner une extension pour tout nombre m rationnel b/a.
Celle-ci a été donnée dans un travail commun de l’orateur avec L.-F. Préville-Ratelle et en fait beaucoup plus généralement, pour tout chemin v formé de pas Nord et Est (voir Trans. AMS, 2017).
Nous montrons ici qu’un tel treillis Tamari(v) est également un maule, ce qui permet d'en donner une nouvelle définition beaucoup plus simple.
Comme pour le premier exposé, le concept de tableaux alternatifs joue un rôle central, mais avec d’autres bijections.
Ces tableaux alternatifs permettent aussi de faire le lien avec le travail très récent de C. Ceballos, A. Padrol et C. Sarmiento, donnant une réalisation géométrique de Tamari(v) étendant le très classique associaèdre associé au Tamari classique.
Il est également amusant de pouvoir définir grâce aux maules un nouveau treillis YTam(λ,v), « mélange » des treillis de Young Y(λ) (voir le premier exposé) et de Tamari(v).
Vendredi 22 septembre : Xavier Viennot http://viennot.org/
Titre : Les maules (1re partie) : Young, pavages et Tamari dans le même panier
Résumé :
Nous introduisons une nouvelle famille d’ensembles partiellement ordonnés, que je propose d’appeler « maule ».
Toute partie du réseau carré engendre un maule par un processus dynamique de particules sauteuses.
Trois treillis (lattices) bien connus sont des maules : les diagrammes de Ferrers Y(λ) inclus dans un diagramme λ donné (partie du treillis de Young), certains pavages sur réseau triangulaire (ou partitions planes) et le très classique treillis de Tamari défini par une notion de « rotation » sur les arbres binaires.
Il en résulte ainsi une nouvelle définition du treillis de Tamari.
Curieusement, le concept de tableau alternatif joue un rôle central dans ce travail.
De tels tableaux ont été introduits dans un tout autre contexte : le modèle très classique du PASEP (partially asymmetric exclusion process) en physique des systèmes dynamiques.
Ces tableaux et leurs avatars ont fait l’objet de nombreux travaux au sein du groupe Combinatoire du LaBRI.
P.-S. : « maule » est un mot Mapuche, (se prononce « ma-ou-lé ») qui désigne la région Maule au Chili, ainsi que le fleuve qui le traverse, (cf. https://fr.wikipedia.org/wiki/Région_du_Maule) région où ce travail a été effectué, grâce à l’invitation de Luc Lapointe de l’Université de Talca.