# Recent impressive combinatorial developments in probability theory

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

1. What have been the most striking and impressive developments along that line in the past decade?
2. Is there an overwhelming agreement in the research community about that statement?
3. What are the most promising avenues of exploration?
4. 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?
-
Do you consider random graphs, percolation theory, etc. as parts of probability theory? –  Algernon Jul 27 '12 at 14:34
@Algernon, thanks for your reply. As a matter of fact, I do. I think the Stroock's statement was more general though because it seemed to imply that fundamental developments of combinatorial nature were occurring (and would continue to occur) throughout probability theory, and not just in areas that were fundamentally at the intersection of probability and combinatorics. I might be mistaken about that of course. I think it would be interesting to add that point to the discussion. –  an12 Jul 28 '12 at 7:28
Regarding question 2: I really don't know what kind of answer you're looking for here. The statement itself is almost too vague to disagree with. I suspect that most probabilists, although they might agree to the statement when presented with it, are unlikely to have given the matter prior thought. –  Mark Meckes Jul 30 '12 at 15:38
@Mark: Thanks a lot for your comments and for bringing up Talagrand's Generic chaining. –  an12 Jul 31 '12 at 9:25

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.

-
@Gil, Thanks a lot for mentioning all these exciting topics. What results/papers did you have in mind when discussing the relation between the stochastic Loewner equations and Ising models (and their critical probabilities)? –  an12 Jul 31 '12 at 9:29
@an12, look for example at these nice lecture notes: arXiv:1109.1549 –  Yvan Velenik Jul 31 '12 at 14:38
@Yvan Velenik, thanks a lot for the lecture notes. They are very interesting to read. –  an12 Aug 1 '12 at 1:18

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.)

-
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).