# Séminaire de Mathématiques Supérieures: Probabilistic Combinatorics

## Topic

Chance has no place in well-planned methodologies. Every *i *should be
dotted, every* t* should be crossed. In combinatorics, at least, nothing
could be further from the truth. Probabilistic methods have played an
ever increasing role in the resolution of combinatorial problems as the
area has developed. In one sense this is unsurprising, as counting is
crucial to combinatorics, and discrete probability is simply counting.
However, the real explanation as to the importance of probabilistic
arguments to the field, and the type of probabilistic arguments
utilized, lies elsewhere.

One of the cornerstones of the probabilistic approach to solving these combinatorial problems is the following guiding principle: information about global structure can be obtained through local analysis; this principle is one of the unifying themes for the summer school. Perhaps the most famous recent example of an application of this principle is the recent proof by Green and Tao that there are arbitrarily long arithmetic progressions in the primes. The proof relies on the fact that forbidding a local structure, to wit an arithmetic progression of length k, in a set of integers, allows us to deduce global "pseudorandom" properties of the set of primes. A key tool in doing so is (a variant of) the celebrated Regularity Lemma of Szemeredi, which was generalized to hypergraphs independently by Gowers and R¨odl. These results also have important applications in graph and hypergraph theory, and several of the speakers are experts in this domain.

Another fundamental "local-to-global" result is the Lov´asz Local Lemma (LLL). This is a version of the probabilistic method by which one can show that some desired, global property (of a random graph, say) holds by showing that in local neighbourhoods, obstructions to the property are moderately unlikely to appear. Due to a recent breakthrough, there is now an efficient randomized algorithm for finding the structure whose existence is guaranteed by the LLL, essentially whenever the lemma applies.

A third important instance of this paradigm is the theory of random walks and rapidly mixing random chains. Here by making and controlling random local choices one can show that one can sample from (a desired probability distribution on) a huge space. At its foundation, this technique relies on the close connection between mixing times of reversible Markov chains (random walks on graphs) and the conductance of such chains. Several of our speakers will present cutting-edge research which uses or develops this perspective.

## Additional Information

Survey:

Please help PIMS to improve the quality of its events and plan for the future by filling out htis quick and painless survey.

Please see the official website at

dms.umontreal.ca/~sms/2012/index_e.php

for further information and updates.

Nikhil Bansal (IBM Research)

Hamed Hatami (McGill University)

Penny Haxell (University of Waterloo)

James R. Lee (University of Washington)

Colin McDiarmid (University of Oxford)

Yuval Peres (Microsoft Research)

Alex Scott (University of Oxford)

**Perla Sousi** (University of Cambridge)

Prasad Tetali (Georgia Institute of Technology)

Eric Vigoda (Georgia Institute of Technology)

**Scientific, Summer School**

**June 25 – July 6, 2012**

**-**