2019-2020

Lundi 9 dťcembre :

Xavier Viennot

Titre : Une bijection insolite pour les arbres binaires 1/2

Rťsumť : We present a bijection, probably new, between binary trees and pairs of vectors (w,h). The first component is the so-called canopy of the binary tree, introduced by Loday and Ronco in relation with some Hopf algebras of trees and permutations. This bijection can be defined directly, but is in fact a by-product of a more general methodology called ę demultiplication of equations in a quadratic algebra Ľ. This methodology can also produce the famous Robinson-Schensted correspondence between permutations and pairs of Young tableaux. We will introduce various concepts such as normal ordering, Wang tilings, Q-tableaux, reverse Q-tableaux, reverse quadratic algebra, planarization of the quadratic equations, demultiplication of equations, from which we will deduce the two above bijections. If time permits we will present other bijections, classical and new, obtained by this same methodology.

reference: Chapters 2 and 4, part III of "ABjC", http://www.viennot.org/abjc.html

Lundi 2 dťcembre :

Andrew Elvey Price and Michael Wallner

Titre : Stretched exponentials for compacted binary trees and a class of minimal automata

Rťsumť : A compacted binary tree is a directed acyclic graph encoding a binary tree in which common subtrees are factored and shared, such that they are represented only once. We show that the number of compacted binary trees of size n is asymptotically given by Theta( n! 4^n e^(3 a_1 n^(1/3)) n^(3/4) ), where a_1 is the largest root of the Airy function and approximately equal to 2.338. Our method involves a new two parameter recurrence which yields an algorithm of quadratic arithmetic complexity for computing the number of compact trees of a given size. We use empirical methods to estimate the values of all terms defined by the recurrence, then we prove by induction that these estimates are sufficiently accurate for large n to determine the asymptotic form of the number of compacted trees. Our results also lead to new bounds on the number of minimal finite automata recognizing a finite language on a binary alphabet showing the appearance of a stretched exponential. This is joint work with Wenjie Fang.

Lundi 25 novembre :

Mehdi Naima

Titre : Families of Monotonic Trees: Enumeration and Asymptotics

Rťsumť : There exists a wealth of literature concerning families of increasing trees. Such models are particularly suitable for representing the evolution of data structures in computer science, or of probabilistic urns in mathematics, but are also particularly adapted to model simple evolutionary trees in biology. An increasing tree is a labeled tree such that, along paths from the root to any leaf (the so-called branches of a tree), node labels are strictly increasing. In particular, no two nodes are allowed to have the same label.

In this paper we introduce new families of increasingly labeled trees that relax the constraint of unicity of each label. Such models are especially adapted to characterize processes evolving in discrete time and in which some nodes can evolve simultaneously. In particular, we obtain growth processes for biology much more adequate than the previous related models.

The families of monotonic trees we introduce are much more delicate to deal with, since they are not decomposable in the sense of Analytic Combinatorics. In particular, new tools are required to study the quantitative statistics of such families. In this paper, we first present a way for specifying such families through evolution processes. In this context, the generating series enumerating the families are formal and thus the quantitative results are not obtained directly. Once the specification is set, we study the tree enumerations and the asymptotic behaviors of the numbers of trees of large size.

Lundi 18 novembre :

Elie de Panafieu https://www.lincs.fr/people/elie-de-panafieu/

Titre : Exact and asymptotic enumeration of directed acyclic graphs work in progress with Sergey Dovgal

Rťsumť : Graphs have a natural decomposition as sets of connected components, while directed graphs exhibit a more complex structure: vertices are gathered into strongly connected components (where an oriented path exists between any pair of vertices), and contracting each of those components to a single vertex results in a Directed Acyclic Graph (DAG: directed graphs containing no oriented cycle). The enumeration of DAGs and strongly connected directed graphs was started by Wright and Liskovets. In this talk, we will recall exact formulas from Robinson and Gessel, relying on interesting generating functions, called graphic or special. We will then present a work in progress with Sergey Dovgal on DAGs asymptotics when the ratio of the numbers of edges and vertices is smaller than or close to 1. Ralaivaosaona, Rasendrahasina and Wagner have recently obtained similar results, even for larger values of this ratio. Previous asymptotic results by Bender, Richmond, Robinson, Wormald, considered either only the number of vertices, or a number of edges proportional to the square of the number of vertices.

Lundi 14 octobre :

P…C

Andrew Elvey Price :

Titre : Elliptic functions in enumerative combinatorics (4)

Rťsumť : Elliptic functions have a rich history in mathematical disciplines ranging from number theory to complex analysis to integrable models in physics. In recent years, a number of problems in enumerative combinatorics have been exactly solved in terms of some sort of elliptic functions, for example: - Certain quadrant walk models (Bernadi, Bousquet-Mťlou and Raschel) - Enumeration of square lattice paths by winding angle (Budd) - Weighted Eulerian orientations on planar maps (Bousquet-Mťlou, E.P. and Zinn-Justin, following Kostov). I will describe a unified framework to solve these problems and more using Jacobi elliptic theta functions. Such solutions are fairly convenient as they allow terms of the sequence to be rapidly computed and also generally yield precise asymptotic and algebraic information about the original series.

In the first part I will describe some fundamental properties of theta functions, and the relevance of some of these properties in the combinatorial setting. As a simple example, I will then show a way to solve a particular quadrant walk model known as Kreweras walks using theta functions. Finally, I will describe some slightly more complicated examples that can be solved using this method, and which can't obviously be solved in a simpler way.

Yvan Le Borgne

Titre : Asymptotic behaviour of the one-dimensional "rock-paper-scissors" cyclic cellular automaton

Rťsumť : The one-dimensional three-state cyclic cellular automaton is a simple spatial model with three states in a cyclic "rock-paper-scissors" prey-predator relationship. Starting from a random configuration, similar states gather in increasingly large clusters; asymptotically, any finite region is filled with a uniform state that is, after some time, driven out by its predator, each state taking its turn in dominating the region (heteroclinic cycles). We consider the situation where each site in the initial configuration is chosen independently at random with a different probability for each state. We prove that the asymptotic probability that a state dominates a finite region corresponds to the initial probability of its prey. The proof methods are based on discrete probability tools, mainly particle systems and random walks. Joint work with Benjamin Hellouin de Menibus. (https://arxiv.org/abs/1903.12622)

Lundi 7 octobre :

Andrew Elvey Price : P…C : Titre : 'Elliptic functions in enumerative combinatorics (3)

Rťsumť : Elliptic functions have a rich history in mathematical disciplines ranging from number theory to complex analysis to integrable models in physics. In recent years, a number of problems in enumerative combinatorics have been exactly solved in terms of some sort of elliptic functions, for example: - Certain quadrant walk models (Bernadi, Bousquet-Mťlou and Raschel) - Enumeration of square lattice paths by winding angle (Budd) - Weighted Eulerian orientations on planar maps (Bousquet-Mťlou, E.P. and Zinn-Justin, following Kostov). I will describe a unified framework to solve these problems and more using Jacobi elliptic theta functions. Such solutions are fairly convenient as they allow terms of the sequence to be rapidly computed and also generally yield precise asymptotic and algebraic information about the original series.

In the first part I will describe some fundamental properties of theta functions, and the relevance of some of these properties in the combinatorial setting. As a simple example, I will then show a way to solve a particular quadrant walk model known as Kreweras walks using theta functions. Finally, I will describe some slightly more complicated examples that can be solved using this method, and which can't obviously be solved in a simpler way.

Jean-FranÁois Marckert

Titre : The combinatorics of the colliding bullets

Rťsumť : The finite colliding bullets problem is the following simple problem: consider a gun, whose barrel remains in a fixed direction; let (Vi)1≤ i≤ n be an i.i.d. family of random variables with uniform distribution on [0,1]; shoot n bullets one after another at times 1,2,..., n, where the ith bullet has speed Vi. When two bullets collide, they both annihilate. We give the distribution of the number of surviving bullets, and in some generalisation of this model. While the distribution is relatively simple, the proof is surprisingly intricate and mixes combinatorial and geometric arguments (Common work with Nicolas Broutin).

Lundi 30 septembre : P…C

Andrew Elvey Price :

Titre : Elliptic functions in enumerative combinatorics (2)

Rťsumť : Elliptic functions have a rich history in mathematical disciplines ranging from number theory to complex analysis to integrable models in physics. In recent years, a number of problems in enumerative combinatorics have been exactly solved in terms of some sort of elliptic functions, for example: - Certain quadrant walk models (Bernadi, Bousquet-Mťlou and Raschel) - Enumeration of square lattice paths by winding angle (Budd) - Weighted Eulerian orientations on planar maps (Bousquet-Mťlou, E.P. and Zinn-Justin, following Kostov). I will describe a unified framework to solve these problems and more using Jacobi elliptic theta functions. Such solutions are fairly convenient as they allow terms of the sequence to be rapidly computed and also generally yield precise asymptotic and algebraic information about the original series.

In the first part I will describe some fundamental properties of theta functions, and the relevance of some of these properties in the combinatorial setting. As a simple example, I will then show a way to solve a particular quadrant walk model known as Kreweras walks using theta functions. Finally, I will describe some slightly more complicated examples that can be solved using this method, and which can't obviously be solved in a simpler way.

Lundi 30 septembre :

Peter McNamara https://www.linux.bucknell.edu/~pm040/index.html

Titre : From Dyck paths to standard Young tableaux

Rťsumť : Dyck paths and standard Young tableaux (SYT) are two of the most central sets in combinatorics. There is a well-known bijection between Dyck paths with 2n steps and SYT of shape (n,n). In recent work, we found nine other bijections between classes of Dyck paths and classes of SYT. I will present my favorites. Along the way, we will encounter connected matchings, non-crossing partitions, non-nesting partitions and oscillating tableaux.

This is joint work with Juan Gil, Jordan Tirrell and Michael Weiner.

Lundi 23 septembre : de 9h30 ŗ 10h30 : (Petite ťcole de combinatoire) : Andrew Elvey Price

Titre : Elliptic functions in enumerative combinatorics (1)

Rťsumť : Elliptic functions have a rich history in mathematical disciplines ranging from number theory to complex analysis to integrable models in physics. In recent years, a number of problems in enumerative combinatorics have been exactly solved in terms of some sort of elliptic functions, for example: - Certain quadrant walk models (Bernadi, Bousquet-Mťlou and Raschel) - Enumeration of square lattice paths by winding angle (Budd) - Weighted Eulerian orientations on planar maps (Bousquet-Mťlou, E.P. and Zinn-Justin, following Kostov). I will describe a unified framework to solve these problems and more using Jacobi elliptic theta functions. Such solutions are fairly convenient as they allow terms of the sequence to be rapidly computed and also generally yield precise asymptotic and algebraic information about the original series.

In the first part I will describe some fundamental properties of theta functions, and the relevance of some of these properties in the combinatorial setting. As a simple example, I will then show a way to solve a particular quadrant walk model known as Kreweras walks using theta functions. Finally, I will describe some slightly more complicated examples that can be solved using this method, and which can't obviously be solved in a simpler way.

Lundi 23 septembre :

Titre :Surfaces ŗ petits carreaux, cartes mťtriques, et volumes de Masur-Veech

Rťsumť : Les surfaces ŗ petits carreaux sont des objets gťomťtriques et combinatoires obtenus en recollant des carrťs le long des cŰtťs. Ces surfaces sont naturellement munies d'une mťtrique plate ŗ singularitťs coniques, et correspondent ŗ des points "entiers" dans l'espace de module des surfaces plates. Le comptage de ces surfaces, pour certains types combinatoires fixťs, permet donc d'ťvaluer le volume de Masur-Veech de ces espaces de modules. Dans un travail joint avec Vincent Delecroix, Peter Zograf, Anton Zorich, nous donnons une formule pour ces volumes, ainsi que plusieurs conjectures concernant les surfaces ŗ petits carreaux en genre grand. Le comptage des surfaces ŗ petits carreaux est effectuť ŗ l'aide du comptage des mťtriques entiŤres sur les cartes combinatoires naturellement associťes ŗ ces surfaces.

Lundi 16 septembre : SebastiŠn Barbieri Lemp https://www.math.ubc.ca/~sbarbieri/

Titre : Topological entropies of SFTs in amenable groups (2/2)

Rťsumť : Given a countable amenable group G, can ask which are the real numbers that can be realized as the topological entropy of a subshift of finite type (SFT). A famous result by Hochman and Meyerovitch completely characterizes these numbers for a two-dimensional infinite grid as those which are right recursively enumerable. I'll show that the same characterization is valid for any amenable group with decidable word problem which admits an action of Z2 which is free and bounded. Using this result we can give a full characterization of the entropies of SFTs for any polycyclic group. Furthermore, the same result holds for any countable group with decidable word problem which contains the direct product of any pair of infinite, finitely generated and amenable groups. In particular, this condition holds for many branch groups such as the Grigorchuk group.

Lundi 9 septembre : SebastiŠn Barbieri Lemp https://www.math.ubc.ca/~sbarbieri/

Titre : Topological entropies of SFTs in amenable groups (1/2)

Rťsumť : Given a countable amenable group G, can ask which are the real numbers that can be realized as the topological entropy of a subshift of finite type (SFT). A famous result by Hochman and Meyerovitch completely characterizes these numbers for a two-dimensional infinite grid as those which are right recursively enumerable. I'll show that the same characterization is valid for any amenable group with decidable word problem which admits an action of Z2 which is free and bounded. Using this result we can give a full characterization of the entropies of SFTs for any polycyclic group. Furthermore, the same result holds for any countable group with decidable word problem which contains the direct product of any pair of infinite, finitely generated and amenable groups. In particular, this condition holds for many branch groups such as the Grigorchuk group.