Séminaire de l'Équipe Modèles Combinatoires

14 janvier 2009 Carine Pivoteau Itération de Newton combinatoire pour le calcul de l'oracle de Boltzmann La génération aléatoire sous le modèle de Boltzmann repose sur les valeurs des séries génératrices en des points intérieurs à leur disque de convergence. Le calcul de ces valeurs est traditionnellement relégué à un “oracle”. Nous produisons un tel oracle pour une grande classe de structures spécifiées par des systèmes combinatoires. Cet oracle repose sur une itération de Newton au niveau des structures combinatoires elles-même, généralisant des travaux de Bergeron, Décoste, Labelle et Leroux. Il en découle aussi un algorithme quasi-optimal pour le calcul des séries génératrices d'énumération.

21 décembre 2008 Jérémie Bouttier Géodésique et cycles cours dans une quadrangulation aléatoire

28 janvier 2009 Amarpreet Rattan Lattice paths below a cyclically shifting boundary The main result I will present is to count the number of lattice paths lying under a cyclically shifting piecewise linear boundary of varying slope. Our main result extends well known enumerative formulae concerning lattice paths, and its derivation involves a classical reflection argument. A refinement allows for the counting of paths with a specified number of corners. We also apply the result to examine paths dominated by periodic boundaries. I will begin by reviewing the classical reflection principle, and then move to the main result.

11 février 2009 Lucas Gerin Automates cellulaires aléatoires : quelques problèmes en dimension 2 Les automates cellulaires tels que présentés ici sont des systèmes de particules définis de façon très simple, mais produisant une très grande variété de comportements. Je me concentrerai sur quelques exemples caractéristiques de la dimension 2, liés par exemple à des questions de marches aléatoires, génération aléatoire et pavages.

18 février 2009 Éric Fusy Enumération des éléments dans les sphères du groupe de Thompson F On peut associer à toute paire d'arbres binaires ayant mêmes nombres de feuilles une transformation de [0,1] dans [0,1], et l'ensemble des transformations ainsi obtenues (muni de la loi de composition) forme un groupe appelé le groupe de Thompson F. Ce groupe peut aussi être formulé en termes de deux générateurs satisfaisant certaines relations. La taille d'un élément de F se définit alors comme la plus petite longueur d'un mot sur les générateurs qui représente l'élément, ou encore la distance à l'élément neutre sur le graphe de Cayley associé. En restant proche de la formulation par arbres binaires, nous montrons comment énumérer efficacement les éléments de F en fonction de la taille.
(Travail en commun avec Murray Elder et Andrew Rechnitzer)

4 mars 2009 Arvind Ayyer Sur la conjecture de Razumov-Stroganov The Razumov-Stroganov conjecture arose in statistical physics as a surprising link between a quantum mechanical one dimensional lattice model called the XXZ spin chain and a completely different combinatorial problem called Fully Packed Loops. This simple-to-state-but-hard-to-prove result has garnered a lot of attention among physicists, combinatorialists and everyone in between since it was first stated in 2001. We formulate the problem from a purely combinatorial point of view and find a new structure which we hope can be exploited towards the correct solution from Erd\H{o}s' book. No previous knowledge will be assumed.
Joint work with Doron Zeilberger

10 mars 2009 Igor Pak Combinatorics and geometry of partition bijections The study of partition identities has a long history going back to Euler, with applications ranging from Analysis to Number Theory, from Enumerative Combinatorics to Probability. Partition bijections is a combinatorial approach which often gives the shortest and the most elegant proofs of these identities. These bijections are then often used to generalize the identities, find “hidden symmetries”, etc. In the talk I will present a modern approach to partition bijections based on the geometry of random partitions and complexity ideas.

26 mars 2009 Nicolas Curien Triangulation aléatoire et arbres grossissants

1 avril 2009 Alexis Darrasse Limiting Distribution for Distances in \(k\)-trees This talk examines the distances between vertices in a rooted \(k\)-tree, for a fixed \(k\), by exhibiting a correspondence with a variety of trees that can be specified in terms of combinatorial specifications. Studying these trees via generating functions, we show a Rayleigh limiting distribution for distances to a random vertex in a random \(k\)-tree: in a \(k\)-tree on n vertices, the proportion of vertices at distance \(d = x*sqrt(n)\) from a random vertex is asymptotic to \((c_k^2*x)/(sqrt(n))*exp(-(c_k^2*x^2)/2)\), where \(c_k=k*H_k\).

8 avril 2009 Vic Reiner Spanning trees and critical groups: the case of line graphs The critical group of a graph is an interesting isomorphism invariant-- a finite abelian group whose cardinality counts the number of spanning trees in the graph, and whose structure is a subtle measure of the graph's complexity. In general, its structure is not well-understood.
After reviewing some of the definitions of the critical group, and some general structural results, we will discuss some precise structural results that relate the critical group of a graph to the critical group of its line graph. One consequence will be that for graphs which are regular (all vertices of the same degree) and nonbipartite, the critical groups for the graph and for its line graph determine each other uniquely in a simple fashion.
This is joint work with Andy Berget, Molly Maxwell, Andy Manion, and Aaron Potechin.

29 avril 2009 Jang-Soo Kim Front representation of set partitions The standard representation of a set partition of \(\{1,2,\ldots,n\}\)is the graph whose vertices are \(1,2,\ldots,n\)and edges are the pairs of two integers in the same block such that there is no other integer between them in the block. We consider another representation, called front representation, which is the graph whose edges are the pairs of two integers in the same block such that one of them is the smallest integer in the block. It turns out that the front representation has several joint symmetric distributions for crossings and nestings as the standard representation does. Using the front representation, we find a recurrence relation for the number of \(12\cdots k12\)-avoiding partitions. Similarly, we find a recurrence relation for the number of \(k\)-distant noncrossing partitions for \(k\leq3\).

13 mai 2009 Matthieu Josuat-Vergès Matrix Ansatz et énumérations de croisements Le but de cet exposé est de montrer comment un calcul matriciel formel permet d'obtenir des séries génératrices comptant des croisements dans divers objets (involutions, partitions d'ensemble, et permutations). Ces calculs matriciels ont deux sortes d'interprétations combinatoires:

par des tableaux (comme les tableaux de permutation, les placements de tours dans des diagrammes de Young)
par des chemins de Dyck ou de Moztkin valués.

Ces méthodes permettent d'obtenir de nouvelles formules explicites pour les séries génératrices.