**Previous talks, of the year and of the previous ones:** see
the slidebar *Talks* at the right hand side.

**Coming talks:**
(scheduled on Mondays from 9:30 to 10:30 (or during the slot of the GT if there is no GT) for the *Petite École de Combinatoire* and from 10:45 to 11:45 for the workgroup, in room 076 by default)

Contact the secretary if you want to propose a talk or to receive announcements.

Calendrier universitaire (des licences) : https://www.u-bordeaux.fr/content/download/75551/583982/version/4/file/Calendrier_Licence_2018-2019.pdf

**2019-2020**

**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 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 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.