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) :


Lundi 18 novembre :

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.

Lundi 21 octobre :

Xavier Viennot

Titre : Une bijection insolite pour les arbres binaires

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, 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",

Cédric Chauve

Titre :Exponentially few RNA structures are designable

Résumé :The problem of RNA design attempts to construct RNA sequences that performs a predefined biological function, identified by several additional constraints. One of the foremost objective of RNA design is that the designed RNA sequence should adopt a predefined target secondary structure preferentially to any alternative structure, according to a given metrics and folding model. It was observed in several works that some secondary structures are undesignable, i.e. no RNA sequence can fold into the target structure while satisfying some criterion measuring how preferential this folding is compared to alternative conformations. We show that the proportion of designable secondary structures decreases exponentially with the size of the target secondary structure, for various popular combinations of energy models and design objectives. This exponential decay is, at least in part, due to the existence of undesignable motifs, which can be generically constructed, and jointly analyzed to yield asymptotic upper-bounds on the number of designable structures.

Work in collaboration with Hua-Ting Yao , Mireille Regnier, Yann Ponty

02/09/2019 en 178 car colloque/workshop

28/10/2019 en 178 car 076 pour le colloque BGW


Muriel Livernet (Université Paris Diderot) AÀP

Titre : Questions combinatoires ouvertes en topologie algébrique au travers des opérades


Pascal Weil


invité de Neuchatel d'Adrian Tanasa et Pascal Weil

Raoul Santachiara (Laboratoire de Physique Théorique et Modèles Statistiques, Université Paris-Sud (Paris-Saclay)) : à confirmer

Vincent Rivasseau (Université Paris-Sud (Paris-Saclay))

à confirmer (demande AAP 2018)

Iain Moffatt (Royal Holloway (université de Londres), Royaume-Uni)

à confirmer (demande AAP 2018)

Laurent Vuillon (LAboratoire de MAthématiques (LAMA), Université Savoie Mont Blanc)

Titre : version combinatoire des mots de la conjecture de Frobenius sur les nombres de Markoff [travaux récents avec C. Reutenauer]

Résumé :

Historique du Groupe de Travail et de Petite École de Combinatoire

Calendrier universitaire :

Jours fériés (susceptibles de concerner un vendredi) : 1er novembre, 11 novembre, 25 décembre, 1er janvier, 1er mai, 8 mai, jeudi de l'Ascension (vers la mi-mai)

Colloque annuel ALEA (vers fin mars) ! 78th Séminaire Lotharingien de combinatoire, Ottrott March 26 - 29 2017, ThibonFest

Friday, jj(th) mmmm: ...

Title: ...

Abstract: ...

plan tranches 1&2

Envoyez un courriel au secrétaire (Olivier Guibert) du Groupe de Travail si vous avez un exposé à présenter.

JCB 2015

journées ALÉA du ... au .../.../2015

Français English




* previous years


edit SideBar