Français >

SMS 2012 - Overview

Deadline to submit your request for financial support: March 1, 2012

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ödl. 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àsz 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.

In the two weeks preceding SMS 2012, the Second Montréal Spring School in Graph Theory (SSGT) will commence. The first half of the second SSGT will consist of two minicourses of ten 90-minute lectures over the course of two weeks. Bruce Reed will give a sequence of ten lectures on graph colouring and the probabilistic method, and notably on the use of the local lemma for proving asymptotically optimal results for graphs. Louigi Addario-Berry will give a sequence of ten lectures on the use of Markov chain mixing, CARP research group Louigi Addario-Berry, Luc Devroye, Bruce Reed meeting, and covering times, and on random walks on random graphs. These two weeks will provide an introduction to some of the probabilistic tools and techniques used in the research to be presented at the SMS. Please see the SSGT 2012 web site for further details.