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

16 mars 2006, 10h30 Eric Fusy Enumération de polytopes Cet exposé décrit les résultats d'un article paru au journal electronique de combinatoire.

23 mars 2006, 10h30 Gilles Schaeffer Polyominos Z-convexes Cet exposé décrit des résultats obtenus avec Enrica Duchi et Simone Rinaldi dans un article disponible sur le serveur arXiv et qui seront présenté au prochain FPSAC.

30 mars 2006, 10h30 Manuel Bodirsky Enumeration of well-nested drawings We study tree-like objects called drawings that have been introduced by computational linguists to capture how natural language syntax trees typically look like. In particular, we present a recursive counting formula for the number of well-nested drawings and an elegant equation for their ordinary generating function, which has close connections to Callan's eigensequence for composition.
Joint work with Daniel Johannsen and Marko Kuhlmann.

5 avril 2006 Katya Vassilieva Cartes bicolores à une face Cet exposé décrit des résultats obtenus avec Gilles Schaeffer et qui seront présentés au prochain FPSAC.

19 avril 2006 Olivier Bernardi Polynome de Tutte et orientations

26 avril 2006 Emmanuel Guitter Arbres continus aléatoires multicritiques

3 mai 2006 Robert Cori Algorithmes de recherche d'arbres couvrants maximaux

17 mai 2006 Hubert de Fraysseix Algorithmes de test de planarité

24 mai 2006 Philippe Nadeau Enumération de tableaux de rubans par les diagrammes de croissance

23 juin 2006 Pierre-Henri Brouard La réductibilité dans le théorème des 4 couleurs

25 octobre 2006 Eric Fusy Algorithmes d'orientation Cet exposé décrit des travaux en cours sur l'unification de différents algorithmes d'orientation de cartes.

15 novembre 2006 Sylvie Corteel Tableaux-permutations et processus d'exclusion partiellement asymétrique The partially asymmetric exclusion process (PASEP) is an important model from statistical mechanics which describes a system of interacting particles hopping left and right on a one-dimensional lattice of N sites. It is partially asymmetric in the sense that the probability of hopping left is \(q\) times the probability of hopping right. Additionally, particles may enter from the left with probability \(\alpha\) and exit from the right with probability \(\beta\).
It has been observed that the (unique) stationary distribution of the PASEP has remarkable connections to combinatorics -- see for example the papers of Derrida, and Duchi and Schaeffer. We prove that in fact the (normalized) probability of being in a particular state of the PASEP can be viewed as a certain weight generating function for permutation tableaux of a fixed shape. (This result implies the previous combinatorial results.) This proof relies on the matrix ansatz of Derrida et al, and hence does not give an intuitive explanation of why one should expect the steady state distribution of the PASEP to involve such nice combinatorics.
Therefore we also define a Markov chain -- which we call the PT chain -- on the set of permutation tableaux which projects to the PASEP in a very strong sense. This gives a new proof of the previous result which bypasses the matrix ansatz altogether. Furthermore, via the bijection from permutation tableaux to permutations, the PT chain can also be viewed as a Markov chain on the symmetric group. Another nice feature of the PT chain is that it possesses a certain symmetry which extends the “particle-hole symmetry” of the PASEP. More specifically, this is a graph-automorphism on the state diagram of the PT chain which is an involution; this has a simple description in terms of permutations.
This is joint work with Lauren Williams (Harvard)

29 novembre 2006 Frédérique Bassino Génération aléatoire d'automates

6 décembre 2006 Pierre Nicodème Analyse de motifs dans les mots

20 décembre 2006 Mathilde Bouvel Plus long motif commun entre deux permutations