Frédérique Bassino, Professor, University Paris13

"Random Generation of Combinatorial Structures"

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.
We will present methods to draw at random combinatorial objects. More precisely, to generate the objects one can use ad hoc methods or generic approaches like Markov chains, the recursive method and Boltzmann samplers.
We will mainly focus on generic generation with the following combinatorial methods :

• 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.
• Boltzamnn samplers, introduced by Duchon, Flajolet, Louchard and Schaeffer, are 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. They generate structures in linear time.