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

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.