2019-2020

Lundi 9 mars : Yvan Le Borgne

Titre : (PEC) Encore une introduction au calcul quantique (de niveau L2).

L'effervescence actuelle au sujet de la construction d'ordinateur quantique incite le ministère à inciter les universités à proposer des formations adaptées. Au LaBRI, il y a eu au moins deux initiatives en plus d'un groupe de travail temporaire. Cyril Gavoille propose des éléments d'information quantique en M1 à l'UFR (http://dept-info.labri.fr/~gavoille/UE-AD/cours-c10.pdf). En M1 à l'ENSEIRB, Géraud Sénizergues avait pris la suite du physicien Yves Leroyer, pour proposer en seconde année une introduction à l'information quantique (http://dept-info.labri.u-bordeaux.fr/~ges/ENSEIGNEMENT/CALCULQ/cours_td_calculq.html). Il a simplifié ce cours pour le rendre accessible en 5x1h20 séances de cours à des étudiants de L2 de la licence internationale. Depuis deux ans j'ai tenté de prendre sa suite en L2. Je me propose de présenter en accéléré le cours actuel.

Plan envisagé (pour la première et potentiellement seule séance):

- Motivations et actualités des constructeurs d'ordinateurs quantiques,

- Variantes sur les circuits logiques,

- Notion abstraite de QBit,

- Une expérience d'interférence proche d'une porte logique quantique,

- Théorème de non-clonage et protocole BB84 (si le temps le permet).

- (Supplément au cours de L2) Evocation des "controverses" actuelles impliquant notamment le scepticisme du combinatoriste Gil Kalai.

Lundi 24 février : Stéphane Dartois

Titre :Products of random matrices and their combinatorics

Résumé :Products of random matrices are important to study the theoretical aspects of fields such as telecommunications engineering, deep neural networks, quantum information theory and quantum chromodynamics at low baryon numbers in physics. Unfortunately it is much more difficult to study products of random matrices than it is random matrices, even in the simplest case of Ginibre ensembles. In this talk I will present different combinatorial problems relating to different interesting ensembles of products of random matrices. I will show how combinatorial results can be used to solve some of the problems posed by the random matrix community and which additional combinatorial questions should be solved to answer more of those questions.

Lundi 17 février : 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

Lundi 10 février : Philippe Duchon

Titre :The search for local infinite search trees

Résumé : Les arbres binaires de recherche (pour des données unidimensionnelles) et quadtrees (pour des données bidimensionnelles) sont des structures de données arborescentes classiques pour représenter des ensembles de valeurs; en ajoutant aux valeurs une dimension de "temps", on peut obtenir un ordre d'insertion qui peut servir à rendre la structure unique. Cette dimension supplémentaire a été utilisée pour "randomiser" les structures de données, cf les "treaps" d'Aragon et Seidel.

Ici on se pose la question suivante: pour un ensemble infini dénombrable de points (dans le plan, pour les arbres binaires de recherche, en consacrant une dimension au temps; dans l'espace, pour les quadtrees), peut-on définir sans ambiguïté une notion d'arbre qui généralise le cas d'un ensemble fini? L'idée est ensuite d'étudier l'arbre obtenu pour des nuages aléatoires de points, mais on se concentre pour l'instant sur des ensembles déterministes.

Une fois écartés des cas où il y a manifestement un obstacle insurmontable à la définition d'un arbre ayant les propriétés souhaitées, on arrive à la conclusion que la situation est différentes pour les arbres binaires de recherche et pour les quadtrees. Pour les premiers, l'arbre binaire de recherche, quand il existe, est toujours unique, et on a des conditions raisonnables pour son existence; en particulier, l'arbre existe avec probabilité 1 dans un processus de Poisson simple dans le demi-plan supérieur. Pour les seconds, le quadtree peut ne pas être unique, et il ne semble pas y avoir de condition simple pour son existence.

Lundi 3 février : Matthieu Rosenfeld

Titre :Evitabilité des cubes additifs sur Z

Résumé : On dit qu'un mot w sur un alphabet constitué d'entiers est un carré additif si il peut s'écrire w=uv tels que u et v sont de même longueur et tels que la sommes des lettres de u soit égal à la somme des lettres de v. De même, un cube additif est un mot de la forme uvw avec u, v et w de même longueur et de même somme. Ainsi, par exemple sur l'alphabet {0,1,2,3}, 103202310 est un cube additif. On dit qu'un mot évite les carrés/cubes additifs si aucun de ses facteurs n'est un carré/cube additif.

Dans mon exposé je m'intéresserai à la question suivante: - Existe-t-il un alphabet finit d'entiers sur lequel on peut construire un mot arbitrairement grand qui évite les cubes/carrés additifs ? Si oui, quels sont ces alphabets ?

Je commencerai par motiver la question en expliquant les liens avec des questions plus générales. Puis, après avoir introduit quelques résultats antérieurs à mes travaux, je présenterai deux de mes résultats. Nous verrons notamment que les cubes additifs sont évitables sur tout les alphabets de taille au moins 4 sauf peut être {0,1,2,3} (et les alphabets équivalents).

Lundi 27 janvier : Jennifer Mc Loud Mann

Titre : Tiling the plane with congruent convex pentagons (part II)

Résumé : In Part II, we discuss some of the history of the search for convex pentagons that admit monohedral tilings of the plane. We will also describe our exhaustive algorithm for finding all pentagons that admit n-block-transitive tilings of the plane.

Lundi 20 janvier : Casey Mann

Titre : Tiling the plane with congruent convex pentagons (part II)

Résumé : In Part I, we will discuss some tiling definitions and combinatorial results concerning convex pentagons that admit monohedral tilings of the plane. The objective is to establish results that, for each positive integer n, allow us to describe an exhaustive algorithm for finding all pentagons that admit n-block-transitive tilings of the plane.

Lundi 13 janvier :

Titre : Three interacting families of Fuss-Catalan posets

Résumé : We will introduce three families of posets depending on a nonnegative integer parameter $m$, having underlying sets enumerated by the $m$-Fuss Catalan numbers. Among these, one is a generalization of Stanley lattices and another one is a generalization of Tamari lattices. We will see how these three families of posets are related in several ways. Indeed, they fit into a chain for the order extension relation and they share some properties. Moreover, we will notice some isomorphisms of posets between specific elements of these posets. Then, we will introduce two associative algebras built as quotients of generalizations of the Malvenuto-Reutenauer algebra. Their products describe intervals of our analogues of Stanley lattices and Tamari lattices. In particular, we will see that one is a generalization of the Loday-Ronco algebra. This is a joint work with S. Giraudo.

Lundi 16 décembre :

Xavier Viennot

Titre : Une bijection insolite pour les arbres binaires 2/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 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.