The Fourth Colloquium on Mathematics and Computer Science is, singularly, the fifth one in a series of events that began at the University of Versailles Saint-Quentin with the ``Colloque Arbres'' in June 1995, then went on to the First and Second Colloquia on Mathematics and Computer Science in September 2000 and 2002, again in Versailles, the fourth edition being hold in Vienna in 2004. These meetings aim at creating a forum for researchers working on the closely related domains of probabilities, trees, algorithms and combinatorics. Basic data structures of Computer Science, such as trees or graphs, can, and should, be studied from several points of view: as the data structure underlying some algorithms, or as a combinatorial or probabilistic object ...
The first meetings in 1995, 2000, 2002 and 2004 were well received both by mathematicians and by computer science researchers, and were followed by a continuously increasing cooperation between both communities. On the one hand, mathematicians found a new source of difficult and interesting questions in the analysis of models for Computer Science. On the other hand, the analysis of algorithms and data structures experienced significant developments with the use of existing tools and methods in probability, statistics and combinatorics, and with the development of new ones. With the organization of the 2006 Colloquium, we hope we made further progress towards establishing a regular meeting place for discussion of topics at the boundary between probabilities, statistics, and fundamental computer science. Papers were sought in a wide spectrum of areas, for instance random trees, stochastic processes, large deviations, branching processes, random walks, discrete probabilities, analytical and enumerative combinatorics, analysis of algorithms and data structures, performance evaluation, random generation of combinatorial structures, and statistics. A large Program Committee, guaranteeing wide coverage of subtopics and expertise in a variety of fields, selected 27 papers for a presentation as 25-minutes talks and 10 other papers were selected for a presentation as posters. All these presentations appear in this volume of proceedings of the journal Discrete Mathematics & Theoretical Computer Science. Furthermore, eight 1-hour invited lectures were presented by Michael Drmota (Vienna), Philippe Flajolet (INRIA), Piotr Indyk (MIT), Grégory Miermont (Orsay), Gilles Schaeffer (École Polytechnique), Laurent Viennot (INRIA), Johan Wästlund (Linköping), Wolfgang Woess (Graz). The invited speakers were free to propose a paper, and that resulted in 4 important contributions to this volume.
Altogether, papers assembled in this volume offer snapshots of current research. At the same time, they illustrate the numerous ramifications of the theory of random discrete structures throughout mathematics and computer science. Many of them, in particular invited lectures, include carefully crafted surveys of their field. I thus hope that this volume may serve both as a reference text and as a smooth introduction to many fascinating aspects of this melting pot of continuous and discrete mathematics.
I wish to express my gratitude and indebtness to the members of the Program Committee who I was honoured to chair, to the members of the Organizing Committee, to the invited speakers and to all the authors and participants of the conference, for each one of them has contributed, in a way or another, to the great success of the conference. I also wish to thank Maxim Krikun for his support, help and advice for the edition of this volume. Jens Gustedt, editor-in-chief of DMTCS, Danièle Gardy, Conrado Martinez, Elahe Zohoorian-Azad and Lucas Gerin were also of a great help.
Last but not least, several public and private institutions provided financial support and other contributions. Special thanks shall be given for the financial and logistic support provided by the Plan Pluriannuel de Formation Informatique, Automatique, Electronique, Electrotechnique Mathématiques (PPF IAEEM), the Centre National de la Recherche Scientifique (CNRS), the Agence Nationale de la Recherche (ANR), the Université Henri Poincaré, the Faculté des Sciences, the Institut Élie Cartan and the city of Nancy.
Nancy, September 2006,
Philippe Chassaing
Chair of the Program Committee
Philippe Chassaing, (Université Henri Poincaré, France)
Brigitte Chauvin (Université de Versailles St-Quentin, France)
Luc Devroye (McGill University, Canada)
Michael Drmota (Vienna University of Technology, Austria)
Danièle Gardy (Université de Versailles St-Quentin, France)
Micha Hofri (Worcester Polytechnic Institute, USA)
Hsien-Kuei Hwang (Academia Sinica, Taiwan)
Philippe Jacquet (INRIA, France)
Svante Janson (Uppsala University, Sweden)
Christian Krattenthaler (Universität Wien, Austria)
Nicholas Pippenger (Princeton, USA)
Jim Pitman (Berkeley, USA)
Philippe Robert (INRIA, France)
