Recent impressive combinatorial developments in probability theory - MathOverflow

Recent impressive combinatorial developments in probability theory

2012-07-27T09:01:50Z

In the preface to the second edition of Daniel Stroock's book "Probability Theory: An Analytic View", there is this striking claim (on p. xv)

... I suspect that, for at least a decade, the most important developments in the field will have a strong combinatorial component ...

I have several questions

What have been the most striking and impressive developments along that line in the past decade?
Is there an overwhelming agreement in the research community about that statement?
What are the most promising avenues of exploration?
Was the progress occurring throughout probability theory and some specific fields such as stochastic processes or statistics or was it confined to areas that were fundamentally combinatorial in nature such as random graph theory?

Answer by Mark Meckes for Recent impressive combinatorial developments in probability theory

2012-07-28T12:50:55Z

While it goes back more than a decade, I think Talagrand's "generic chaining"/"majorizing measures without measures" approach to bounding suprema of stochastic processes could be considered a striking development along those lines. (It's definitely striking; the subjectivity is in how "combinatorial" you consider the generic chaining to be.)

Answer by Mark Lewko for Recent impressive combinatorial developments in probability theory

2012-07-28T17:50:55Z

One example along these lines is the problem of estimating the probability that a discrete random matrix is singular. Let $P_n$ denote the probability that a $n \times n$ matrix with random $\pm 1$ entries is singular. A well-known conjecture states that $P_n = (1/2 + o(1))^n$. In 1967 Komlos proved that $P_n =o(1)$ and in 1995 Kahn, Komlos and Szemeredi proved that $P_n \ll (1-c)^n$ for $c=.042$. In 2005 Tao and Vu proved $P_n \ll (3/4+o(1))^n$. A main ingredient in this approach is a Freiman-type inverse theorem based on additive combinatorics. More recently this has been improved to $P_n \ll (1/\sqrt{2}+o(1) )^n$ by Bourgain, Vu and Wood (which also uses a Freiman-type inverse theorem).

Answer by Gil Kalai for Recent impressive combinatorial developments in probability theory

2012-07-30T12:38:00Z

A whole body of results in probability with strong combinatorial flavour are around 2-dimensional stochastic models. Some of this progress started 15 years ago but much was achieved in the last decade. Much of this research has combinatorial flavour. This includes conformal invariance for planar percolation on the triangular grid; The stochastic Lowevner equations, SLE, and their relations with Brownian motion, crirical percolation, loop-erased random walks, the Ising model, and other models. These relations allowed the computation of many critical exponents of 2D models. You can add to that the recent results on self avoiding random walks (again in 2D), and the computation of critical probabilities for 2D Potts model.

Answer by Gil Kalai for Recent impressive combinatorial developments in probability theory

2012-07-30T12:49:18Z

Another important development in probability theory with strong combinatorial flavour and relations to mathematical physics is around random partitions. This is closely related to random surfaces and random matrices. The origin are again older but much was achieved in the last decade or so.