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

16 janvier 2008 Marni Mishna Combinatorial notions of D-finiteness A series is D-finite if it satisfies a linear differential equation with polynomial coefficients. The class includes algebraic and rational functions, both of which have very nice combinatorial representations using generating functions of context free languages and regular languages respectively. In this talk, we will explore combinatorial interpretations of D-finite functions. First, we shall consider lattice paths in restricted regions, and then we shall consider the types of formal languages that arise when we add the (disjoint) shuffle product to our expressive power. We will describe a system that can achieve any D-finite series.

23 janvier 2008 Nicolas Broutin Structure des arbres couvrants minimaux et graphes aléatoires L'arbre couvrant minimal d'un graphe pondéré représente une sorte de squelette du reseau qui peut-être utilisé pour approximer des problèmes difficiles ou comme support à un réseau plus dense. Dans les deux cas, sa structure et la distance typiques entre les noeuds influencent la qualité des applications. Nous nous plaçons dans le cas où le graphe sous-jacent est complet et pondéré de manière aléatoire. Nous étudions les liens qui existent entre l'arbre couvrant minimal et de nombreuses structures fondamentales telles que les graphes aléatoires de Erdos-Renyi, les arbres récursifs et les arbres simplement générés. Nous en déduisons l'ordre de grandeur des distances dans l'arbre couvrant minimal.
Travail en collaboration avec L. Addario-Berry et B. Reed.

30 janvier 2008 Eric Fusy Tracés optimaux avec arêtes brisées, d'après Zhang

6 février 2008 Frank Nielsen Vers une géométrie algorithmique de l'information Multi-dimensional heterogeneous data sets are ubiquituous in visual computing (eg., image classification, face recognition, texture synthesis, etc.). For example, in image recognition or classification, various low-level features are first extracted and stacked onto a high-dimensional vector encoding the individual image properties. In these high dimensional Cartesian product spaces, it becomes challenging to guess by ad-hoc methods (meaning hard-coding distances in the software) the “right” distance measure. This is all the more problematic as the Euclidean distances or other classic norms fail in most cases. A novel algorithmic trend consists in learning from the data sets themselves the most appropriate distance function belonging to a class of measures.In order to solve the task at hand, this implies that the latter algorithm has to work for *any* member of the distance class.
In this talk, I will consider the class of information-theoretic Bregman divergences that are axiomatically neatly characterized as generalizing least-square projections. Bregman divergences are not necessarily symmetric distortions that encapsulate the (squared) Euclidean distance and the relative entropy. This makes it very attractive since Bregman-compliant algorithms will be able to handle indifferently geometric or statistical data sets (eg, histograms or parametric distributions). We review our recent work on generalizing core geometric algorithms to the class of Bregman divergences:

Centroids and barycenters, and center-based k-means clustering
Circumcenter of the smallest enclosing ball
Voronoi and dual regular triangulations

If time permits, I'll show that these Bregman divergences are the canonical distance measures in dually flat spaces that generalize the Euclidean geometry under the auspices of differential information geometry.
Joint work with Jean-Daniel Boissonnat, INRIA Geometrica and Richard Nock, UAG CEREGMIA.
References:

Bregman Voronoi Diagrams: Properties, Algorithms and Applications, http://arxiv.org/abs/0709.2196 (SODA'07)
On the Centroids of Symmetrized Bregman Divergences, http://aps.arxiv.org/abs/0711.3242 (2007)
On the smallest enclosing information disk. Inf. Process. Lett. 105, 3 (Jan. 2008), 93-97, 10.1016/j.ipl.2007.08.007
On approximating the smallest enclosing Bregman Balls. SCG '06, 10.1145/1137856.1137931

Applets at http://www.sonycsl.co.jp/person/nielsen/applets.html

13 février 2008 Pierre Nicodème Comptage de mots; inclusion-exclusion, automates; loi limite; complexité

20 février 2008 Guillaume Chapuy Une bijection pour les cartes couvertes sur les surfaces orientables Une carte couverte de genre g est une carte de genre g, munie d'une sous-carte couvrante à une face (la sous-carte pouvant avoir n'importe quel genre entre 0 et g). On présentera une bijection entre les cartes couvertes, certaines orientations, et des paires formées d'un arbre et d'une carte à une face bipartie. Cela généralise la construction donnée par Olivier Bernardi dans le cas planaire, et permet d'obtenir de jolie formules, exactes et asymptotiques.
Travail commun avec O. Bernardi.

19 mars 2008 Robert Cori Hypercartes et permutations connexes

2 avril 2008 Axel Bacher Périmètre de site moyen des animaux dirigés sur réseau carré par la méthode des empilements de pièces Les animaux dirigés forment une sous-classe d'animaux (un animal est une partie connexe et finie d'un graphe), qui ont été dénombrés par Dhar en 1983. Le périmètre de site d'un animal dirigé est le nombre de « voisins », ou sites qui ne sont pas dans l'animal mais qu'on peut lui rajouter tout en restant un animal dirigé. Nous nous intéresserons au périmètre de site moyen des animaux d'aire, ou nombre de points, fixée. Nous utiliserons une bijection, due à Bétréma et Penaud, entre les animaux dirigés et d'autres objets : des empilements de pièces.

9 avril 2008 Matthieu Josuat-Vergès Permutations, orientations acycliques, et motifs évités Nous allons mettre en correspondance trois sortes d'objets : des permutations (à ensemble d'excédences fixés), des orientations acycliques de graphes, et enfin des diagrammes de Young remplis de 0 et de 1 en évitant certains motifs.
Les tableaux de permutations font le lien entre la première et la troisième classe d'objets, ici le motif évité est une paire de matrices d'ordre 2. En prenant une autre paire de matrices d'ordres 2, on fait élémentairement le lien entre la deuxième et la troisième classe.
Reste à voir que les motifs évités sont équivalents, au sens où ils s'énumèrent de la même façon, ce qui peut se faire par récurrence mais aussi par des bijections. Selon le temps restant, nous montrerons que cette correspondance s'étend à une classe de polyominos bien plus générale que celle des diagrammes de Young.

7 mai 2008 John Irving Star factorizations

1er octobre 2008 Robert Cori Sur la probabilité d'être connexe d'une permutation à \(k\) cycles

8 octobre 2008 Luca Castelli Aleardi Forêt de Schnyder pour les triangulations de genre supérieur

15 octobre 2008 Gilles Schaeffer Sur un probleme de construction de graphes a voisinage contraint

22 octobre 2008 Alex Postnikov Polypositroids Positroids are a special kind of matroids associated to totally positive cells on the Grassmannian. We investigate these matroids (and their generalizations) in terms of matroid polytopes. They correspond to an interesting class of convex polytopes that have remarkable combinatorial properites. In particular, they are related to triangulations of the product of two simplices, to non-crossing trees, and to Stasheff's associahedron and cyclohedron. They also seem to be related to Fomin-Zelevinsky's theory of cluster algebras and generalized associahedra.
Based on a joint work with Thomas Lam.

5 novembre 2008 Valentin Feray Interprétation combinatoire explicite des coefficients des polynomes de Kerov Les polynômes de Kerov expriment les valeurs des caractères irréductibles du groupe symétrique en fonction des cumulants libres. Grace à une formule donnant les caractères comme une somme sur des graphes bicolores, ces polynômes peuvent être interprétés combinatoirement. Cela fait intervenir un énoncé proche du lemme des mariages et des équations de transport.

19 novembre 2008 Marie Albenque Convergence de grandes triangulations en pile Une “triangulation en pile” est obtenue de manière récursive par ajout de sommets et d'arêtes à partir d'un triangle initial. Une grande partie de mon expose sera consacree a la convergence sous la loi uniforme des triangulations en pile renormalisees vers l'arbre continu d'Aldous puis j'evoquerai d'autres resultats concernant notamment la convergence locale sous la loi uniforme et le comportement sous la loi induite par la construction recursive de telles triangulations.

24 novembre 2008 Cyril Nicaud Génération aléatoire de sous-groupes finiment engendrés d'un groupe libre Je présenterai un algorithme efficace pour générer aléatoirement et uniformément les sous-groupes finiment engendrés d'un groupe libre de rang fini, pour une taille fixée. La taille d'un tel sous-groupe est ici définie comme étant le nombre de sommets dans sa représentation par un graphe réduit, obtenu par la méthode de réduction de Stallings. Pour cela, on utilisera des méthodes de la combinatoire analytique : méthode symbolique, théorème du col et la méthode récursive de génération aléatoire. L'algorithme de génération obtenu est de complexité moyenne linéaire, dans le modèle RAM.
Travail effectué avec Frédérique Bassino et Pascal Weil.

10 décembre 2008 Emmanuel Guitter Distances entre 3 sommets dans une quadrangulation aléatoire

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.