TEN YEARS!

✍ Scribed by Michal Karoński; Joel Spencer

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 45 KB
• Volume: 16
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(200001)16:1<1::aid-rsa1>3.0.co;2-e

✦ Synopsis

of Random Structures & Algorithms made its appearance in early 1990. We pause for a moment's reflection and celebration of our tenth anniversary.

Mathematics is anything but a static subject. Areas wax and wane, merge, and bifurcate. In the 1980s a new area was emerging. It took from discrete math, from probability, and from theoretical computer science. While the study of random structures and random algorithms could formally be placed in probability theory, the centrality of the discrete and the particular nature of graph-theoretic and computer science questions gave it a flavor all its own. Such were our thoughts and fortunately John Wiley proved willing to take a chance with this new venture. In the 1990s our hopes have been realized. Ten years after, along with the biennial Poznań Random Structures & Algorithms meeting there are now numerous conferences with titles such as Probabilistic Combinatorics that are devoted to our subject matter. Theorems and conjectures are flourishing and we are pleased to see many of the best results appearing in these pages.

Some highlights: Janson's Inequality, one of the most applied of the modern probabilistic methods, was discovered by Svante Janson at the August 1987 Random Structures & Algorithms meeting in Poznań. His first paper [6] (jointly with Tomasz Łuczak and Andrzej Ruciński) appeared in the volume for that conference. Later papers, especially [4], were published in Random Structures & Algorithms itself. In 1990 Ed Bender, Ed Canfield and Brendan McKay [3] gave an asymptotic formula for the number of connected graphs with n vertices and e edges. They were aided by a three page gem of Tomasz Łuczak [9] that gave bounds very close to their formula. In 1991 József Beck [2] presented an algorithmic version of one of the most important tools of probabilistic combinatorics-the Local Lemma; in the same issue the parallel version of this result was given by Noga Alon [1]. In 1993 Svante Janson, Donald Knuth, Tomasz Łuczak and Boris Pittel [5] published a monumental paper, our only single paper issue to date, probing deeply into the phase transition of the random graph G n p at p = n -1 + λn -4/3 . In 1994 Bob Robinson and Nick Wormald [11] proved that almost all regular graphs are hamiltonian and introduced so called analysis of variance method. In 1995 Jeong Han Kim [8] showed the existence of a triangle free graph on n vertices with no independent set of size n 1/2 ln 1/2 n, resolving the asymptotics of the Ramsey function R 3 k and ending a 60-year quest. His proof used many of the modern probabilistic techniques and in 1997 he was awarded the Fulkerson prize for this work. In 1996 Jim Propp and David Wilson published a paper [10] on the coupling from the past (CFTP) algorithm for so called exact or perfect simulation. A very few papers published in Random Structures & Algorithms (or anywhere else!) for the last few years have had such vast and immediate impact: the work of Propp and Wilson has been followed up in at least 30 to 40 papers by perhaps two dozen researchers. Finally, rapidly mixing Markov chains have led to many remarkable results including the volume 1