Recent impressive combinatorial developments in probability theory - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T01:21:09Z http://mathoverflow.net/feeds/question/103284 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103284/recent-impressive-combinatorial-developments-in-probability-theory Recent impressive combinatorial developments in probability theory an12 2012-07-27T09:01:50Z 2012-08-01T08:38:15Z <p>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)</p> <blockquote> <p>... I suspect that, for at least a decade, the most important developments in the field will have a strong combinatorial component ...</p> </blockquote> <p>I have several questions</p> <ol> <li>What have been the most striking and impressive developments along that line in the past decade?</li> <li>Is there an overwhelming agreement in the research community about that statement?</li> <li>What are the most promising avenues of exploration?</li> <li>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?</li> </ol> http://mathoverflow.net/questions/103284/recent-impressive-combinatorial-developments-in-probability-theory/103381#103381 Answer by Mark Meckes for Recent impressive combinatorial developments in probability theory Mark Meckes 2012-07-28T12:50:55Z 2012-07-28T12:50:55Z <p>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.)</p> http://mathoverflow.net/questions/103284/recent-impressive-combinatorial-developments-in-probability-theory/103400#103400 Answer by Mark Lewko for Recent impressive combinatorial developments in probability theory Mark Lewko 2012-07-28T17:50:55Z 2012-07-28T17:50:55Z <p>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 <a href="http://www.ams.org/mathscinet/search/publdoc.html?r=1&amp;pg1=CNO&amp;s1=221962&amp;loc=fromrevtext" rel="nofollow">Komlos proved</a> that $P_n =o(1)$ and in 1995 <a href="http://www.ams.org/mathscinet/search/publdoc.html?r=1&amp;pg1=CNO&amp;s1=1260107&amp;loc=fromrevtext" rel="nofollow">Kahn, Komlos and Szemeredi proved</a> that $P_n \ll (1-c)^n$ for $c=.042$. In 2005 <a href="http://arxiv.org/abs/math/0501313" rel="nofollow">Tao and Vu</a> 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 <a href="http://arxiv.org/abs/0905.0461" rel="nofollow">Bourgain, Vu and Wood</a> (which also uses a Freiman-type inverse theorem).</p> http://mathoverflow.net/questions/103284/recent-impressive-combinatorial-developments-in-probability-theory/103512#103512 Answer by Gil Kalai for Recent impressive combinatorial developments in probability theory Gil Kalai 2012-07-30T12:38:00Z 2012-07-30T12:38:00Z <p>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.</p> http://mathoverflow.net/questions/103284/recent-impressive-combinatorial-developments-in-probability-theory/103513#103513 Answer by Gil Kalai for Recent impressive combinatorial developments in probability theory Gil Kalai 2012-07-30T12:49:18Z 2012-07-30T12:49:18Z <p>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.</p>