Projet GAMMA nov200710
Génération Aléatoire: Modèles, Méthodes, Algorithmes
Laboratoires Participants
 Dominique Rossin
 Enrica Duchi
 Jeremy Lovejoy
 Roberto Mantaci
 Anne Micheli
 Thi Ha Duong Phan
 Dominique Poulalhon
 Olivier Mallet
 Mathilde Bouvel
 Michèle Soria
 Olivier Bodini
 Maryse Pelletier
 Carine Pivoteau
 Alexis Darrasse
 Olivier Roussel
 Lucas Gerin
 Yann Ponty
The goal of this project, "random generation: models, methods and algorithms", is to develop a set of fundamental methods and algorithms for the random generation of complex combinatorial structures. such objects appear in a variety of applications, especially in computer science.
Random generation plays an important role in domains dealing with enormous volumes of data, for example in interaction networks (computer, sociological, biological networks); in this case, random generation allows the comparison of models and the evaluation of their adequacy for real data. random testing and model checking are two additional fields of application for random generation. one of the main issues there arises when choosing appropriate data for testing, and designing efficient methods for fast generation of this data. in many cases the problem can be described in terms of graphs or automata, so that the data are specified as paths, or words. in these cases where intensive generation is required, the samplers have to be very efficient.
Our objective is to study all the steps leading to the realization of efficient generators for complex combinatorial structures.
More precisely, we shall particularly focus on:
 maps that are used in algorithmic geometry as well as in statistical physics,
 automata and words of regular languages that play a central role in text algorithms and in pattern matching,
 pattern avoiding permutations that are linked with phonetics,
 plane overpartitions related to hypergeometric series and super Schur functions,
 permutation tableaux coming from the enumeration of cells of the Grassmanian and related to statistical physics.
One of the methods to study the properties of combinatorial objects consists of finding bijections with simpler objects like, for example, decomposable structures. Decomposable structures can be recursively specified using combinatorial constructions such as union, product, sequence, cycle, set. These operations are then directly translated into operations between the corresponding generating functions. A convenient formalization of the approach of decomposable structures is the concept of object grammars (Dutour, Fedou), that allows the description of objects using very general kinds of operations.
An alternative approach for enumerating combinatorial objects is Eco method (Barcucci, Del Lungo, Pergola, and Pinzani) that provides a recursive construction of the objects according to their size. Each object is obtained from a smaller one by making some local expansions. If the recursive construction presents a certain regularity, then it can be encoded in a formal system called succession rule, from which one can often obtain the generating function of the objects themselves. When two ECO constructions lead to the same succession rule, they can be used to determine bijections between classes of different combinatorial objects.
This analysis of combinatorial properties of the objects enables us to give recognition algorithms for our objects, useful for generation with rejection for instance, and perhaps efficient transformation algorithms between our complex objects and simpler ones, in order to exhaustively or randomly generate them.
To generate the objects themselves one can use an ad hoc method or generic approaches like Markov chains, the recursive method and Boltzmann samplers.
The recursive method due to Nijenhuis and Wilf allows both exhaustive and random generation. It was systematized by Flajolet, Zimmermann and Van Custem to treat decomposable structures. It is implemented in the packages Combstruct of Maple and CS of MuPad.
A new methodology, Boltzamnn samplers, was introduced by Duchon, Flajolet, Louchard and Schaeffer. It is based on the idea that an object receives a probability essentially proportional to an exponential of its size. A Boltzmann generator is a program randomly generating objects according to this probability distribution. It has been shown, that operations on decomposable structures are associated to operations on the generators. Theoretical as well as practical results show that the complexity of generation is linear as soon as small variations in size are allowed.
Another goal of our project is the development of the algorithmics of random generation and, in particular, algorithms related to Boltzmann model. We want to extend generic algorithms to
 make multicriteria random generation,
 take into account new specifications,
 control numerical approximations and the loss of uniformity induced,
 use discrete rather than floating point versions of these algorithms.
Finally, we shall validate this approach by the implementation of algorithms dedicated to the main models considered.
Our project is mainly based on the productive synergy between combinatorial and algorithmic tools required to attain our objectives.

22/10/2009 LIAFA
 Dominique Rossin :
Théorème de Stanley Wilf Marcus Tardos et questions ouvertes  Cyril Nicaud :
Familles d'ensembles et de partitions avec petites traces
 Dominique Rossin :
 06/11/2009 LIAFA
Réunions passées

15/01/2009
 Olivier Bodini :
Génération de Boltzmann pour les structures colorées  Lucas Gerin :
Automates cellulaires : quelques problèmes de simulation
 Olivier Bodini :

11/12/2008
 Carine Pivoteau :
Itération de Newton combinatoire pour le calcul de l'oracle de Boltzmann
 Carine Pivoteau :

1213/11/2008
Journées permutations, combinatoire et génération aléatoire 
28/03/2008
 Frédérique Bassino :
Génération aléatoire de sousgroupes finiment engendrés d'un groupe libre  Cyril Nicaud :
Génération aléatoire d'automates déterministes et accessibles
 Frédérique Bassino :

22/02/2008
 Alessandra Carbone :
Quelques exemples de génération aléatoire de structures en bioinformatique  Alain Denise :
Quelques algorithmes de génération aléatoire de structures en bioinformatique
 Alessandra Carbone :

22/10/2007
 Jean Mairesse :
Méthode à la Propp et Wilson pour la génération aléatoire  Enrica Duchi :
La méthode ECO
 Jean Mairesse :

03/10/2007
 Dominique Poulalhon :
Méthode à la Propp et Wilson pour la génération aléatoire  Carine Pivoteau :
Générateurs de Boltzmann
 Dominique Poulalhon :
 14/09/2007
 Workshop on Analytic Algorithmics and Combinatorics  ANALCO'09
January 3, 2009, New York
(colocated with the ACMSIAM Symposium on Discrete Algorithms  SODA'09)  ALEA 2009
 20th International Conference on Analytical, Combinatorial, and Asymptotic
Methods for the Analysis of Algorithms  AofA'09
June 1419, 2009, Frejus (France).  FPSAC 2009
 PP 2009