Pacific Institute for the Mathematical Sciences - PIMS

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.

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.