Dynamical critical site percolation on the triangular lattice has exceptional times

You need to know: Graph, infinite graph, connected subgraph of a graph, basic probability theory, exponential distribution with parameter $\lambda$ .

Background: The triangular grid is the (infinite) graph G whose vertex set is $V \subset {\mathbb R}^2$ given by $V=\{(k+m/2, \sqrt{3}m/2)\,|\, k,m \in {\mathbb Z}\}$ , and two vertices are connected by an edge if and only if the distance between them is $1$ . Assume that each vertex of G, independently of other vertices, (i) is coloured black or white at time $t=0$ , with probability $1/2$ for each colour, (ii) generate a random variable $T$ according to exponential distribution with parameter $\lambda=1/2$ , wait for time $T$ , and switch the colour, and (iii) repeat part (ii) again and again. This is called the dynamical critical site percolation on the triangular grid G. If, at some moment $t=t_0$ , graph G has an infinite connected subgraph consisting on only white vertices, we say that percolation occurs. Let ${\cal T}$ be the set of all times $t\in[0,1]$ at which percolation occurs.

The Theorem: On 29th April 2005, Oded Schramm and Jeffrey Steif submitted to arxiv a paper in which they proved that, with probability $1$ , the set ${\cal T}$ is non-empty.

Short context: Site percolation is an important model in mathematics for studying processes such as diffusion. It is studied for various grids, such as triangular, square, etc. In the triangular grid model described above, it is known that at any fixed $t_0>0$ , the probability that percolation occurs at time $t=t_0$ is $0$ . The Theorem states, however, that, with probability $1$ , there is a non-empty set ${\cal T}$ of exceptional times at which percolation occurs.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 10.3 of this book for an accessible description of the Theorem.

Go to the list of all theorems

The “Majority Is Stablest” conjecture is true

You need to know: Set $\{-1,1\}^n$ of sequences $x_1, \dots, x_n$ such that each $x_i$ is either $-1$ or $1$ . Notation $[n]$ for set $\{1,2,\dots,n\}$ , notation $\text{sign}(x)$ for the sign of real number x.

Background: Boolean function is a function $f:\{-1,1\}^n \to \{-1,1\}$ . Denote $E[f] = \frac{1}{2^n}\sum\limits_{x\in \{-1,1\}^n}f(x)$ the average value of f. For $i\in [n]$ , let $N_i(f)$ be the number of $x=(x_1, x_2, \dots, x_n)\in \{-1,1\}^n$ , sich that $f(x)\neq f(x_1,\dots,x_{i-1},-x_i,x_{i+1},\dots,x_n)$ . Ratio $\text{Inf}_i(f)=N_i(f)/2^n$ is called the influence of i. Equivalently, $\text{Inf}_i(f) = \sum\limits_{S\subset[n], i\in S}\hat{f}(S)^2$ , where $\hat{f}(S)=\frac{1}{2^n}\sum\limits_{x\in \{-1,1\}^n}\left[f(x)\prod\limits_{i\in S}x_i\right]$ . For $0\leq \rho \leq 1$ , the noise stability of f is $S_\rho(f)=\sum\limits_{S\subset[n]}\rho^{|S|}\hat{f}(S)^2$ .

The Theorem: On 23rd March 2005, Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz submitted to arxiv a paper in which they proved that for any $0 \leq \rho \leq 1$ and $\epsilon>0$ there exists a $\delta>0$ such that if $f:\{-1,1\}^n \to \{-1,1\}$ satisfies $E[f]=0$ and $\text{Inf}_i(f) \leq \delta$ for all i, then $S_\rho(f) \leq \frac{2}{\pi}\arcsin(\rho)+\epsilon$ .

Short context: For the majority function $\text{Maj}_n(x)=\text{sign}\left(\sum\limits_{i=1}^n x_i\right)$ (we may assume that n is odd to guarantee that $\sum\limits_{i=1}^n x_i \neq 0$ ), we have $\lim\limits_{n \to \infty}S_\rho(\text{Maj}_n) = \frac{2}{\pi}\arcsin(\rho)$ . Thus, the Theorem states that the majority function has (in the limit $n\to\infty$ and up to $\epsilon$ ) the highest noise stability among all functions with $E[f]=0$ and low influence. This statement has been conjectured by Khot, Kindler, Mossel, and O’Donnell, and was known as the “Majority Is Stablest” conjecture. In has applications to the analysis of voting systems and to algorithmic complexity for some combinatorial problems.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 10.1 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Random Bernoulli n by n matrix is singular with probability at most (3/4+o(1))^n

You need to know: Matrix, determinant $\text{det}(M)$ of square matrix M, singular square matrix (matrix with determinant $0$ ), basic probability theory, independent and identically distributed (i.i.d.) random variables, $o(1)$ notation.

Background: Let $M_n$ be a random $n \times n$ matrix whose entries are i.i.d. Bernoulli random variables (each entry is equal to $+1$ or $-1$ with probabilities $1/2$ ). Let $P_n = P(\text{det}(M_n) = 0)$ be the probability that $M_n$ is singular.

The Theorem: On 5th November 2004, Terence Tao and Van Vu submitted to the Journal of the AMS a paper in which they proved that $P_n \leq \left(\frac{3}{4}+o(1)\right)^n$ as $n\to\infty$ .

Short context: The question of estimating $P_n$ has attracted considerable attention in literature. In 1967, Komlós proved that $\lim\limits_{n\to\infty} P_n = 0$ . In 1995, Kahn, Komlós, and Szemerédi proved that $P_n=O(0.999^n)$ . This was later improved by Tao and Vu to $P_n=O(0.958^n)$ . The Theorem provides a much better upper bound.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Shape theorem holds in Kesten-Sidoravicius model for the infection spread

You need to know: Integer lattice ${\mathbb Z}^d$ , continuous time simple random walk on ${\mathbb Z}^d$ , jump rate, independent identically distributed (i.i.d.) random variables, Poisson distribution, almost sure convergence, compact convex set.

Background: At time $0$ , let us put $n_x$ “A-particles” at each $x\in{\mathbb Z}^d$ , where $n_x$ are i.i.d. random variables following Poisson distribution with mean $\mu$ . We also put a finite number of “B-particles” in arbitrary (non-random) positions on ${\mathbb Z}^d$ . Then each A-particle and each B-particle performs a continuous time simple random walk on ${\mathbb Z}^d$ , with jump rates $D_A$ and $D_B$ , respectively. The walks are independent, except that when a B-particle and an A-particle coincide, the latter turns into the former. Bet $B'(t)$ be the set of all locations $x\in{\mathbb Z}^d$ visited by a B-particle during $[0,t]$ , and let $B(t) = B'(t)+[-1/2, 1/2]^d$ .

The Theorem: On 31st December 2003, Harry Kesten and Vladas Sidoravicius submitted to arxiv a paper in which they proved the existence of a nonrandom, compact, convex set $B_0 \subset {\mathbb R}^d$ such that for all $\epsilon > 0$ , inclusion $(1-\epsilon)B_0 \subset \frac{1}{t}B(t) \subset (1+\epsilon)B_0$ holds almost surely as $t\to\infty$ .

Short context: In the model above, B-particles model organisms affected by an infection, A-particles model unaffected organisms, and the Theorem proves that in the limit the region affected by infection converges to a non-random shape growing at linear rate.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 8.6 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Two values for the chromatic number of a random graph G(n,d/n)

You need to know: Graph, vertices, edges, chromatic number of a graph, limits, basic probability theory, independent events.

Background: Let $G(n,p)$ denote random graph with n vertices, such that every possible edge is included independently with probability p. For a fixed $d>0$ , consider sequence of random graphs $G\left(n,\frac{d}{n}\right)$ with $n\to\infty$ .

The Theorem: On 9th October 2003, Dimitris Achlioptas and Assaf Naor submitted to the Annals of Mathematics a paper in which they proved that, with probability that tends to 1 as $n\to\infty$ , the chromatic number of $G\left(n,\frac{d}{n}\right)$ is either $k_d$ or $k_d+1$ , where $k_d$ denotes the smallest integer k such that $d<2k\log k$ .

Short context: Chromatic number is one of the most important and well-studied invariants of a graph, and it is natural to ask what it is equal to for random graphs. In 1991, Luczak proved that for every $d>0$ there exists a constant $k_d$ , such that, with probability that tends to 1 as $n\to\infty$ , the chromatic number of $G\left(n,\frac{d}{n}\right)$ is either $k_d$ or $k_d+1$ . However, the exact value of $k_d$ remained unknown. The Theorem answers this question.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 5.11 of this book for an accessible description of the Theorem.

Go to the list of all theorems

An asymptotic form of the Satisfiability Threshold Conjecture is true

You need to know: Supremum, infinum, big O and small o notations, boolean variables, their disjunction, conjunction, and negation, satisfiable and unsatisfiable formulas, basic probability theory: select objects from finite set uniformly, independently and with replacement.

Background: A k-clause is a disjunction of k Boolean variables, some of which may be negated. For a set $V_n$ of n Boolean variables, let $C_k(V_n)$ denote the set of all $2^kn^k$ possible k-clauses on $V_n$ . A random k-CNF formula $F_k(n, m)$ is formed by selecting uniformly, independently and with replacement m k-clauses from $C_k(V_n)$ and taking their conjunction. For each $k \geq 2$ , let $r_k$ be the supremum of r such that $F_k(n, rn)$ is satisfiable with probability tending to 1 as $n\to\infty$ .

The Theorem: On 4th September 2003, Dimitris Achlioptas and Yuval Peres submitted to the Journal of the AMS a paper in which they proved the existence of a sequence $\delta_k$ convergent to $0$ such that for all $k \geq 3$ , $r_k \geq 2^k \log 2 - (k + 1)\frac{\log 2}{2} - 1 - \delta_k.$

Short context: For each $k \geq 2$ , let $r^*_k$ be the infinum of r such that $F_k(n, rn)$ is unsatisfiable with probability tending to 1 as $n\to\infty$ . Obviously, $r_k \leq r_k^*$ . The Satisfiability Threshold Conjecture predicts that in fact $r_k = r_k^*$ for all $k\geq 3$ . Because it is known that $r_k^* \leq 2^k\log 2$ , the Theorem implies that $r_k = r_k^*(1-o(1))$ , which is an asymptotic form of the Satisfiability Threshold Conjecture.

Links: The original paper is available here.

Go to the list of all theorems

The Lieb conjecture on the monotonicity of Shannon’s entropy is true

You need to know: Basic probability theory: random variable, its support, probability density function, expectation (denoted $E[.]$ ), independent random variables, identically distributed random variables.

Background: For a random variable X with probability density function f and support $S\subset{\mathbb R}$ , its Shannon entropy is $\text{Ent}(X) = -\int_S f(x) \log f(x) dx$ . Random variable X is square-integrable if $E[X^2]<\infty$ .

The Theorem: On 4th September 2003, Shiri Artstein, Keith Ball, Franck Barthe, and Assaf Naor submitted to the Journal of the AMS a paper in which they proved that, for any sequence $X_1, X_2, \dots$ of independent and identically distributed square-integrable random variables, the entropy of the normalised sum $\text{Ent} \left(\frac{X_1 + \dots + X_n}{\sqrt{n}}\right)$ is a non-decreasing function of n.

Short context: For sequence $X_1, X_2, \dots$ as above, it is known that normalised sums $Y_n = \frac{1}{\sqrt{n}}\sum\limits_{i=1}^n X_i$ converge to normal distribution. In 1949 Shannon proved that $\text{Ent}(Y_2) \geq \text{Ent}(Y_1)$ . In 1978, Lieb conjectured that in fact $\text{Ent}(Y_{n+1}) \geq \text{Ent}(Y_n)$ for all n, which could be interpreted that $Y_n$ becomes closer and closer to the normal distribution (the one with maximal entropy) at every step. This conjecture was open even for $n=2$ . The Theorems proves it in full.

Links: The original paper is available here.

Go to the list of all theorems

The Alon’s second eigenvalue conjecture is true

You need to know: Basic probability theory, random permutation, graph, d-regular graph, adjacency matrix of a graph, eigenvalue of a matrix, limits.

Background: For an even $d \geq 4$ , by random d-regular graph on n vertices we mean a graph formed from $d/2$ uniform, independent permutations on $\{1, . . . , n\}$ . For fixed d and fixed real $\epsilon>0$ , let $p_n$ be the probability that such a graph has the second largest eigenvalue of its adjacency matrix greater than $2 \sqrt{d-1} + \epsilon$ .

The Theorem: On 27th March 2002, Joel Friedman submitted to Memoirs of the AMS a monograph in which he proved that $\lim\limits_{n\to\infty} p_n = 0$ .

Short context: The adjacency matrix of any finite undirected graph G has only real eigenvalues, which can be written in non-increasing order $\lambda_1(G) \geq \lambda_2(G) \geq \dots \geq \lambda_n(G)$ . For d-regular G, $\lambda_1(G)=d$ . In 1986, Alon observed that graphs G with $\lambda_2(G)$ small have various nice properties, and conjectured that for any $\epsilon>0$ and any $d\geq 3$ , $\lambda_2(G) \leq 2 \sqrt{d-1} + \epsilon$ for “most” random d-regular graphs G. The constant $2 \sqrt{d-1}$ in this inequality is the best possible. This statement became known as Alon’s second eigenvalue conjecture. The Theorem, as stated above, resolves it for even d. In the same paper, Friedman also proved the conjecture for other models of random d-regular graph, including models for odd d.

Links: Free arxiv version of the original paper is here, the published version is here.

Go to the list of all theorems

(log t)^(2/3) law holds for the two dimensional asymmetric simple exclusion process

You need to know: Set ${\mathbb Z}^2$ of points $x=(x_1, x_2)$ with integer coefficients, probability, independent random variables, exponential distribution, covariance $\text{cov}(X,Y)$ of random variables X and Y.

Background: At time $t=0$ , let us put, for each $x\in {\mathbb Z}^2$ , a particle in site x, independently and with probability $1/2$ . Then, for each particle p, independently generate a random variable $t_p$ from exponential distribution, wait for time $t_p$ , and then jump to an adjacent site up, down, or right, with probabilities $1/4, 1/4, 1/2$ , respectively, provided that the target site is unoccupied (and otherwise stay). This action is then repeated and performed in parallel for all particles. We call this asymmetric simple exclusion process (ASEP). For any $x\in {\mathbb Z}^2$ , let $\eta_x(t)$ be the number of particles (which can be $0$ or $1$ ) in position x at time t. Next define $D(t) = \frac{4}{t}\sum\limits_{x \in {\mathbb Z}^2} x_1^2 \cdot \text{cov}(\eta_x(t), \eta_{(0,0)}(0))$ , where $x_1$ is the first coordinate of x.

The Theorem: On 31st January 2002, Horng-Tzer Yau submitted to the Annals of Mathematics a paper in which he proved the existence of a constant $\gamma>0$ such that, for sufficiently small $\lambda>0$ , $\lambda^{-2}|\log \lambda|^{2/3}e^{-\gamma|\log\log\log \lambda|^2} \leq \int_0^{\infty}e^{-\lambda t}t D(t)dt \leq \lambda^{-2}|\log \lambda|^{2/3}e^{\gamma|\log\log\log \lambda|^2}.$

Short context: ASEP is one of the simplest models for modelling diffusion process, function $D(t)$ defined above is known as diffusion coefficient, and understanding how fast $D(t)$ grows with t is important for estimating the speed of diffusion process. The Theorem implies that $D(t)$ grows approximately as $(\log t)^{2/3}$ for large t, and can therefore be called “ $(\log t)^{2/3}$ law for ASEP”.

Links: The original paper is available here. See also Section 4.3 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Probability that Wiener sausages intersection volume is large decays fast

You need to know: d-dimensional Euclidean space ${\mathbb R}^d$ , volume in ${\mathbb R}^d$ , limits, basic probability theory, stochastic processes, independent stochastic processes, Wiener process in ${\mathbb R}^d$

Background: Let $W(t)$ be standard Wiener process in ${\mathbb R}^d$ . For $a>0$ and $t \geq 0$ , let $W_a(t) = \{ x \in {\mathbb R}^d \,|\,\exists s \in [0,t] : \rho(x,W(s)) \leq a \}$ , where $\rho$ is the distance in ${\mathbb R}^d$ . $W_a(t)$ is known as Wiener sausage. Let $S^a(t) = W_1^a(t) \cap W_2^a(t)$ be the intersection of two Wiener sausages corresponding to two independent Wiener processes starting at origin, and let $|S^a(t)|$ be its (d-dimensional) volume.

The Theorem: On 28th November 2001, Michiel van den Berg, Erwin Bolthausen and Frank den Hollander submitted to Annals of Mathematics a paper in which they proved that for every $a>0$ and $b>0$ , $\lim\limits_{t\to\infty}\frac{1}{t^{(d-2)/d}}\log P(|S^a(bt)|\geq t) = -C_{a,d,b}, \, d \geq 3$ where P denotes the probability, and $C_{a,d,b}>0$ is some constant depending on a, d, and b. Similarly, $\lim\limits_{t\to\infty}\frac{1}{\log t}\log P(|S^a(bt)|\geq t/\log t) = -C_b, \, d=2$ .

Short context: Let $a$ be fixed and denote $V_t=|S^a(t)|$ . The Theorem implies that, for large t, $P(V_{bt} \geq t)$ decays as $\text{exp}\left(-C t^{(d-2)/d}\right)$ for $d \geq 3$ . In other words, the probability that Wiener sausages intersection volume is large (larger than t after time bt) decays exponentially fast in t, with constant in the exponent $\frac{d-2}{d}$ . This gives us a good idea how the distribution of $V_t$ looks like. The Theorem resolves open questions asked by Khanin, Mazel, Shlosman, and Sinai in 1994.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 1.1 of this book for an accessible description of the Theorem.

Go to the list of all theorems