2019-2020

Lundi 6 juillet : Henri Derycke

Titre :Une restriction pour un polynôme de Tutte sur la grille infinie.

Résumé : Dans le cas des graphes finis, le polynôme de Tutte est un invariant bivarié se spécialisant en plusieurs autres invariants de graphe comme le polynôme chromatique. Il peut se définir par une somme sur les arbres couvrants du graphe pondérée par deux statistiques : les activités interne et externe au sens de Tutte du graphe. En s'intéressant à des arbres couvrants dont la racine serait placée à l'infini dans une direction, je propose dans cet exposé un analogue (sommable) de cette définition sur le graphe infini $Z^2$: la série génératrice pour une période donnée des forêts couvrantes périodiques selon cette période, d'une généralisation des activités des arêtes du domaine fondamental. Les marginales du polynôme ont alors le bon goût d'être égales et invariantes au changement de direction des racines bien que leur loi jointe en dépende. Ce travail est notamment motivé par l'étude de configurations bipériodiques récurrentes dans le modèle du tas de sable sur la grille $Z^2$ qui sont en bijection avec ces forêts périodiques. Il s'agit d'un travail en commun avec Yvan Le Borgne.

Enregistrement


Lundi 22 juin : Thomas Fernique

Titre :Pavages par coupe et projection définis par des motifs

Résumé : La méthode de coupe et projection permet d'obtenir de jolis pavages en discrétisant des sous-espaces affines. Par exemple, les mots strumiens peuvent s'obtenir en discrétisant une droite du plan. Les pavages de Penrose peuvent s'obtenir en discrétisant un plan dans l'espace à 5 dimensions. On se pose ensuite la question (motivée par l'étude des quasicristaux en physique) : quand est-ce qu'un pavage obtenu ainsi peut être caractérisé uniquement par ses motifs finis ? En d'autres termes : quand peut-on décrire uniquement localement la structure globale du pavage ? L'exposé sera a priori plutôt introductif, avec un survol des résultats obtenus ces dernières années en collaboration avec Nicolas Bédaride.

Enregistrement


Lundi 25 mai : Timothy Budd (Radboud University)

Titre :Essentially irreducible maps and Weil-Petersson volumes

Résumé : I will discuss the enumeration of certain maps on a genus-g surface, g ≥ 0, with n faces of prescribed even degrees with a girth constraint. More precisely I consider maps that have no vertices of degree one and that are essentially 2b-irreducible for b ≥ 0 meaning that simple contractible cycles of length 2b or less are disallowed unless they bound a single face of degree 2b. Using results of Bouttier & Guitter I will show that such maps are counted by polynomials in b and the face degrees and that the polynomials satisfy recursion relations ("string" and "dilaton" equations) in n. This generalizes a result by Norbury in the absence of the irreducibility constraint. Next, I will show that the leading orders in b of these polynomials are related to the Weil-Petersson volumes of hyperbolic surfaces with geodesic boundary components (at least when g=0,1). If time permits I will comment on a special case where this relation can be understood bijectively.

Enregistrement


Lundi 18 mai : Guillaume Chapuy

Titre :Polynômes de Jack, cartes non-orientables, et b-positivité

Résumé : Je parlerai du papier arXiv:2004.07824 que l'on vient de mettre sur l'arxiv avec Maciek Dołęga (Académie des sciences de Pologne). Il est classique en combinatoire qu'il existe un lien entre cartes (orientables), permutations, et via la théorie des représentations, fonctions de Schur. En 1996 Goulden et Jackson on formulé la "b-conjecture" qui dit que ce lien subsiste si l'on remplace les fonctions de Schur par des polynômes de Jack, qui en sont une déformation à un paramètre (appelé "b"). Cette conjecture est ouverte et difficile, car la théorie des représentations ne marche plus! Dans ce travail avec Maciek, nous faisons un progrès substantiel vers la b-conjecture, et en fait on fait un peu plus, en étudiant la "fonction tau" des constellations sur des surfaces non-orientables, et sa b-déformation. Notre preuve utilise, d'un côté, des équations "à la Tutte", de l'autre de la combinatoire des tableaux type "règles de Pieri", et aussi beaucoup de travail. Le but de l'exposé sera au moins d'énoncer et de situer le résultat, et de donner une idée de ce qui intéressant dans ce qu'on a fait, voire dans la preuve.

Enregistrement


Lundi 11 mai : Amélie Trotignon

Titre :Fonctions harmoniques discrètes dans les trois-quarts de plan

Résumé : Les fonctions harmoniques discrètes jouent un rôle important en probabilités et sont fortement reliées à l’énumération de marches aléatoires. La transformation de Doob est un moyen de construire un processus aléatoire conditionné dans un cône à partir d’un processus aléatoire et une fonction harmonique positive s’annulant au bord du cône. Trouver des fonctions harmoniques positives associées à des processus aléatoires est donc un objectif naturel dans l’étude des marches aléatoires confinées. Il y a très peu de moyens de calculer des fonctions harmoniques discrètes. Dans cet exposé nous nous intéressons aux fonctions harmoniques discrètes aux conditions de Dirichlet dans les trois quarts de plan. Tandis que les marches (aléatoires) dans le quart de plan ont été très étudiées, le cas des marches évitant un quadrant n’a été développé que récemment. Nous étendons la méthode du quart de plan — résolution d’une équation fonctionnelle via un problème frontière à l’aide de transformations conformes — aux trois-quart de plan en appliquant la stratégie de découper le domaine en deux cônes symétriques. Nous obtenons une expression explicite simple de la fonction génératrice algébrique des fonctions harmoniques associées aux marches aléatoires évitant un quadrant.

Enregistrement


Lundi 4 mai : Pascal Weil

Titre :Statistics of subgroups of the modular group

Résumé :The modular group PSL(2,Z) plays an important role in geometry, among other reasons because it is a standard example of a group acting discretely by isometries on the hyperbolic plane. The statistics of finite index subgroups of PSL(2,Z) have been widely studied: exact and asymptotic computation of the number of index n subgroups, asymptotic behavior of the isomorphism type of these subgroups (Hall, Stothers, Muller and Schlage-Puchta).

We extend these results to all finitely generated subgroups of PSL(2,Z). The key tool is a representation of a subgroup H by a finite labeled graph Gamma(H) subject to certain combinatorial conditions, called the Stallings graph of H. The number of vertices of Gamma(H), which we take to be the size of H, coincides with its index if H has finite index. The combinatorial constraints characterizing Stallings graphs of subgroups of PSL(2,Z) allow us to count the subgroups of size n and to give a random generation algorithm for size n subgroups (finite index subgroups, free subgroups). We also give an asymptotic behavior of the number of such groups and compute the probability that a size n subgroup is free or has finite index. Finally, we give large deviations result on the isomorphism type of these subgroups.

The methods used belong to analytic combinatorics.

This is joint work with Frédérique Bassino and Cyril Nicaud.

Enregistrement


Vendredi 10 avril à 14 h30 : Natasha Morrison

Titre : Invertibility of Random Symmetric Matrices

Résumé : A well-known conjecture states that a random symmetric n*n matrix with entries in {-1,1} is singular with probability of order (n^2)/(2^n). In this talk I will describe some recent work where we prove that the probability of this event is at most 1/exp(Omega(n^1/2)). This improves the previous best known bound of 1/exp(Omega(n^1/4*(log n)^1/2)), which was obtained by Ferber and Jain. Our main theorem is an inverse Littlewood-Offord theorem in Zp^n, which is inspired by the method of hypergraph containers. This is joint work with Marcelo Campos, Leticia Mattos and Rob Morris.


Lundi 6 avril : Eric Fusy

Titre :Intervalles de Tamari généralisés et cartes planaires orientées

Résumé : La combinatoire des intervalles de Tamari, initiée par Chapoton, est une domaine très actif depuis une dizaine d'années, avec de riches propriétés énumératives. En particulier une construction due à Bernardi et Bonichon (s'appuyant sur les bois de Schnyder) établit une bijection entre intervalles de Tamari de taille n et triangulations à n sommets internes. Le treillis de Tamari a été récemment étendu par Préville-Ratelle et Viennot aux treillis dits de nu-Tamari, et dans ce contexte on parle d'intervalles de Tamari généralisés. Fang et Préville-Ratelle ont montré que les intervalles généralisés sont en bijection avec les cartes planaires non-séparables, par une approche bijective à base d'arbres étiquetés de parcours en profondeur. Nous montrerons ici deux autres approches bijectives. La première s'appuie sur les décompositions séparantes de quadrangulations et est une extension de la bijection de Bernardi et Bonichon. La seconde spécialise la bijection de Bernardi et Bonichon aux intervalles de Tamari dits synchronisés, qui s'identifient aux intervalles généralisés. Travail en commun avec Abel Humbert.


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 :

Camille Combe https://sites.google.com/view/camillecombe/accueil

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

slides


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

slides


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.

Part 1 : Introduction to Jacobi theta functions - analytic and algebraic properties

Part 2: Quadrant walks in terms of Jacobi theta functions

Part 3: Modular properties of Jacobi theta functions; asymptotics and algebraicity results

Part 4: New results - examples showing more types of equations that can be solve

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.

Part 1 : Introduction to Jacobi theta functions - analytic and algebraic properties

Part 2: Quadrant walks in terms of Jacobi theta functions

Part 3: Modular properties of Jacobi theta functions; asymptotics and algebraicity results

Part 4: New results - examples showing more types of equations that can be solve

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.

Part 1 : Introduction to Jacobi theta functions - analytic and algebraic properties

Part 2: Quadrant walks in terms of Jacobi theta functions

Part 3: Modular properties of Jacobi theta functions; asymptotics and algebraicity results

Part 4: New results - examples showing more types of equations that can be solve


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.

Part 1 : Introduction to Jacobi theta functions - analytic and algebraic properties

Part 2: Quadrant walks in terms of Jacobi theta functions

Part 3: Modular properties of Jacobi theta functions; asymptotics and algebraicity results

Part 4: New results - examples showing more types of equations that can be solve


Lundi 23 septembre :

Élise Goujard (IMB) https://sites.google.com/site/elisegoujard/

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.


Français English

Groupe

Événements

GT

* Années précédentes

Ressources

edit SideBar