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

- Start Date: 06/25/2012
- End Date: 07/06/2012

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)

Université de Montréal

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.

Louigi Addario-Berry (McGill University)

Luc Devroye (McGill University)

Bruce Reed (McGill University)

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.