The betweenness centrality of all graph vertices can be computed in O(nm) time

You need to know: Basic graph theory (graphs, vertices, edges, shortest path), $O(.)$ notation.

Background: Let $\sigma_{s,t}$ be the total number of shortest paths from s to t in an undirected graph G. Let $\sigma_{s,t}(v)$ the number of such shortest paths which contain vertex v. The number $C_B(v) = \sum\limits_{s \neq v \neq t} \frac{\sigma_{s,t}(v)}{\sigma_{s,t}}$ is called the betweenness centrality of vertex v.

The Theorem: On 25th September 2000, Ulrik Brandes submitted to The Journal of Mathematical Sociology a paper in which he developed an algorithm which compute the betweenness centrality of all vertices of graph with n vertices and m edges in time $O(nm)$ .

Short context: The betweenness centrality is important in the analysis of social networks. However, before the Theorem, the fastest algorithm to compute it worked in $O(n^3)$ steps. The Theorem provides a significant improvement for graphs with not too many edges, which is often the case in the applications.

Links: The original paper is available here.

Go to the list of all theorems

Robbins conjecture on the number of vertically symmetric ASMs is true

You need to know: Product notation $\prod\limits_{i=1}^n$ , matrices.

Background: An $n \times n$ matrix with elements $a_{ij}$ is called an alternating-sign matrix (ASM) if (i) all $a_{ij}$ are equal to -1, 0, or 1, (ii) the sum of elements in each row and column is 1, and (iii) the non-zero elements in each row and column alternate in sign. An ASM is called (a) vertically symmetric (VSASM) if $a_{ij}=a_{i,n+1-j}$ for all i,j; (b) half-turn symmetric (HTSASM) if $a_{ij}=a_{n+1-i, n+1-j}$ for all i,j; (c) quarter-turn symmetric (QTSASM) if $a_{ij} = a_{j,n+1-i}$ for all i,j. Let $A(n), A_V(n), A_{HT}(n)$ and $A_{QT}(n)$ denote the number of $n \times n$ ASMs, VSASMs, HTSASMs, and QTSASMs, respectively. It is known that $A(n) = (-3)^{\frac{n(n-1)}{2}}\prod\limits_{i=1}^n \prod\limits_{j=1}^n\frac{3(j-i)+1}{j-i+n}.$

The Theorem: On 24th August 2000, Greg Kuperberg submitted to arxiv a paper in which he proved that $A_V(2n+1) = (-3)^{n^2} \prod\limits_{i=1}^{2n+1} \prod\limits_{j=1}^n \frac{3(2j-i)+1}{2j-i+2n+1}$ . In addition, $A_{HT}(2n)=A(n) \cdot (-3)^{\frac{n(n-1)}{2}} \prod\limits_{i=1}^n \prod\limits_{j=1}^n \frac{3(j-i)+2}{j-i+n}$ , and $A_{QT}(4n) = A_{HT}(2n)\cdot A(n)^2.$

Short context: Alternating-sign matrices are important both in pure mathematics (determinant computation) and applications (so-called “six-vertex model” for ice modelling in statistical mechanics). The formula for $A(n)$ was conjectured by Robbins and Rumsey in 1986 and proved by Zeilberger in 1996. In 1991, Robbins conjectured formulas for the number of ASMs with various symmetries, including VSASMs, HTSASMs, QTSASMs, and others. The Theorem proves a large portion of these conjectures and opens the road to the resolution of the remaining ones in the subsequent work.

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

Go to the list of all theorems

The Julia set of typical quadratic map is locally connected and has measure zero

You need to know: Basic complex analysis, set ${\mathbb C}$ of complex numbers, absolute value $|z|$ of complex number z, boundary of a set, locally connected set, set of Lebesgue measure zero, the notion of (Lebesgue) almost every.

Background: For polynomial $f:{\mathbb C} \to {\mathbb C}$ , let $K_f \subset {\mathbb C}$ be the set of points $z_0\in {\mathbb C}$ such that the sequence $z_0, z_1=f(z_0), z_2=f(z_1), \dots, z_{n+1}=f(z_n), \dots$ is bounded, that is, $|z_n|\leq B, \, \forall n$ for some $B \in {\mathbb R}$ . The boundary $J_f$ of $K_f$ is called the Julia set of f.

The Theorem: On 17th August 2000, Carsten Petersen and Saeed Zakeri submitted to the Annals of Mathematics a paper in which they proved that for almost every complex number c with $|c|=1$ , the Julia set of quadratic polynomial $f(z)=z^2+cz$ is locally connected and has Lebesgue measure zero.

Short context: Julia set is a fundamental concept in the theory of complex dynamics, because it consists of values $z_0$ such that an arbitrarily small perturbation can cause significant changes in the sequence of iterated function values. The Theorem describes the geometry of Julia sets for almost all quadratic polynomials. In fact, Petersen and Zakeri also gave a precise arithmetic sufficient condition on c for the theorem conclusion to hold.

Links: The original paper can be found here.

Go to the list of all theorems

Largest eigenvalue of X’X, with x_ij i.i.d. normal, approaches the Tracy–Widom law

You need to know: Limits, derivatives, integrals, independent random variables, standard normal distribution $N(0,1)$ , cumulative distribution function (cdf), convergence in the distribution, matrices, transpose $X'$ of matrix $X$ , matrix multiplication, eigenvalues of a matrix.

Background: Let $A(x)=\frac{1}{\pi}\int_0^\infty \cos\left(\frac{t^3}{3}+xt\right) dt$ , and $q(x)$ be the (unique) function such that $q''(x)=xq(x)+2q^3(x)$ and $\lim\limits_{x\to+\infty}\frac{q(x)}{A(x)}=1$ . The probability distribution with cdf $F(s) = \exp\left(-\frac{1}{2}\int_s^\infty (q(x) + (x-s)q^2(x)) dx\right), s \in {\mathbb R}$ is called the Tracy–Widom law of order 1.

Let X be an $n \times p$ matrix whose entries are independent and follow $N(0,1)$ . Let $l_{np}$ be the largest eigenvalue of matrix $X'X$ . Let $\mu_{np} = \left(\sqrt{n-1}+\sqrt{p}\right)^2$ and $\sigma_{np} = \left(\sqrt{n-1}+\sqrt{p}\right)\left(\frac{1}{\sqrt{n-1}}+\frac{1}{\sqrt{p}}\right)^{1/3}$ .

The Theorem: In August 2000, Iain Johnstone submitted to the Annals of Statistics a paper in which he proved that, if $n=ak$ , $p=bk$ , where $a\geq b$ are constants and $k\to\infty$ , then $\frac{l_{np}-\mu_{np}}{\sigma_{np}}$ converges in the distribution to the Tracy–Widom law of order 1.

Short context: Understanding the distribution of eigenvalues of random matrices is the problem of fundamental importance both in mathematics and in many of its applications. In a series of papers in 1993-1996, Tracy and Widom proved that the maximal eigenvalue of random square matrices (in several important models of randomness), appropriately scaled, converges to an explicit distribution which have got the name Tracy–Widom law. The Theorem generalises this result to rectangular matrices.

Links: The original paper can be found here.

Go to the list of all theorems

Set of m n-variate degree-d polynomials has at most (emd/n)^n zero patterns

You need to know: Field, polynomial over field, multivariate polynomials and their degrees, factorial $n!= 1\cdot 2 \cdot \dots \cdot n$ , notation ${N}\choose{M}$ $= \frac{N!}{M! (N-M)!}$ , base of natural logarithms $e$ .

Background: Let $f_1,...,f_m$ be a sequence of polynomials in n variables of degree at most d over a field F, where $m \geq n$ . The zero-pattern of this sequence at $u\in F^n$ is the set of indexes i ( $1 \leq i \leq m$ ) for which $f_i(u) = 0$ .

The Theorem: On 25th July 2000, Lajos Rónyai, László Babai, and Murali Ganapathy submitted to the Journal of the AMS a paper in which they proved that the number of zero-patterns (as u ranges over $F ^n$ ) is at most ${md-(d-2)n}\choose{n}$ for all $d\geq 1$ and $m \geq n$ .

Short context: Estimates for the number of zero-patterns are useful, for example, in the complexity analysis of so-called “quantifier elimination algorithms”. Motivated by this application, Heintz proved in 1983 that this number is at most $(1+md)^n$ . The Theorem implies upper bound $\left(\frac{emd}{n}\right)^n$ , which is better by a factor of $(n/e)^n$ . In fact, the authors show that, under some reasonable conditions, the bound in the Theorem is optimal up to the factor of $(7.25)^n$ .

Links: The original paper can be found here.

Go to the list of all theorems

The Lagarias-Wang finiteness conjecture is false

You need to know: Matrix, square matrix, (complex) eigenvalue of a square matrix, absolute value of a complex number, $\limsup$ .

Background: The spectral radius $\rho(A)$ of a square matrix A is the largest absolute value of an eigenvalue of A. Let $\Sigma$ be a finite set of $n \times n$ matrices. Let $\rho_k(\Sigma)=\max\{\rho(A_1 A_2 \dots A_k)^{1/k}, \, A_i \in \Sigma, \, i=1,2,\dots,k\}$ . The quantity $\rho(\Sigma) = \limsup\limits_{k\to\infty} \rho_k(\Sigma)$ is called the generalized spectral radius of $\Sigma$ .

The Theorem: On 11th July 2000, Thierry Bousch and Jean Mairesse submitted to the Journal of the AMS a paper in which they proved, among other results, the existence of a finite set $\Sigma$ of matrices (in fact, $\Sigma$ can consist of two $2 \times 2$ matrices) such that $\rho(\Sigma) > \rho_k(\Sigma)$ for all $k \geq 0$ .

Short context: The generalized spectral radius is an important concept useful in a wide range of contexts. It is known that $\rho(\Sigma) \geq \rho_k(\Sigma)$ for all $k \geq 0$ . In 1995, Lagarias and Wang conjectured that, for every $\Sigma$ , there is a k such that $\rho(\Sigma) = \rho_k(\Sigma)$ . This statement became known as the finiteness conjecture. The Theorem disproves this conjecture.

Links: The original paper can be found here.

Go to the list of all theorems

Szemeredi’s theorem holds with doubly exponential bound

You need to know: Integers, addition, multiplication, power, logarithm, set, subset, size of set.

Background: Here, by arithmetic progression of length k we mean a sequence $a_1, a_2, \dots, a_k$ such that $a_n = a_1 + (n-1)d$ , $n=1,2,\dots, k$ , for some $d \neq 0$ .

The Theorem: In March 2000, Timothy Gowers submitted to Geometric and Functional Analysis (GAFA) a paper in which he proved that, for every positive integer k, every subset of $\{1, 2, \dots ,N\}$ of size at least $N(\log \log N)^{-c}$ , where $c=2^{-2^{k+9}}$ , contains an arithmetic progression of length k.

Short context: In 1975, Szemerédi proved that for any positive integer k and any $\delta > 0$ , there exists a positive integer $N = N(k, \delta)$ such that every subset of the set $\{1, 2, \dots ,N\}$ of size at least $\delta N$ contains an arithmetic progression of length k. This famous theorem is one of the milestones of combinatorics. However, the bound for N which follows from Szemerédi’s proof is huge. The Theorem proves that Szemeredi’s theorem holds with $N=\exp(\exp(\delta^c))$ .

Links: The original paper can be found here.

Go to the list of all theorems

Constant-degree expanders construction based on zig-zag product

You need to know: Direct product $\times$ , graph, vertex set, edges, neighbours, edge expansion of a graph, family of expanders.

Background: For any graph G, a 2-edge path is a set of vertices $i,k,j$ , connected by edges $i-k$ and $k-j$ . Now, the graph $G^2$ is the graph with the same vertices as G such that for every 2-edge path $i,k,j$ in G, we put an edge between i and j in $G^2$ .

Denote [N] the set of integers $1,2,\dots, N$ . We say that graph G is D-regular if each vertex has D neighbours; it is also D-coloured if its edges are marked with labels from [D] such that no 2 edges with the same mark share a vertex. For a label $i \in [D]$ and a vertex v let v[i] be the neighbour of v along the edge marked i.

Let $G$ be a $D_1$ -regular $D_1$ -coloured graph on $[N_1]$ , and $H$ be a $D_2$ -regular $D_2$ -coloured graph on $[D_1]$ . Then zig-zag product $G \cdot_Z H$ of $G$ and $H$ is a $D_2$ -regular graph on $[N_1] \times [D_1]$ defined as follows: For all $v \in [N_1]$ , $k \in [D_1]$ , $i, j \in [D_2]$ , the edge $(i, j)$ connects the vertex $(v, k)$ to the vertex $(v[k[i]], k[i][j])$ .

The Theorem: On 10th July 2000, Omer Reingold, Salil Vadhan, and Avi Wigderson submitted to Annals of Mathematics a paper in which they proved that the sequence given by $G_1=H^2$ , $G_{i+1}=G_i^2\cdot_Z H, i\geq 1$ (where H is d-regular graph of size $d^4$ and sufficiently high edge expansion) is a $d^2$ -regular family of expanders.

Short context: Explicit and efficient constructions of families of expanders with various “good” properties have applications in many areas of mathematics and computer sciences. There are many such constructions starting from 1973 work of Margulis, but, before 2000, all the constructions were either algebraic or complicated. The Theorem provides a simple combinatorial construction of a family of constant-degree expanders.

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

Go to the list of all theorems

The norms of bilinear Hilbert transforms are uniformly bounded

You need to know: Limits, derivative, k-th derivative $z^{(k)}(t)$ , integration, $L^p$ norm $\|z\|_p= \left( \int_{-\infty}^{\infty} |z(t)|^p dt \right)^{1/p}$ .

Background: Function $z:{\mathbb R}\to{\mathbb R}$ is called a Schwartz function if there exist all derivatives $z^{(k)}(t)$ for all $k=1,2,3,\dots$ and all $t\in{\mathbb R}$ , and, for every k and $\gamma\in{\mathbb R}$ , there is a constant $C(k,\gamma)$ such that $|t^\gamma z^{(k)}(t)| \leq C(k,\gamma), \, \forall t\in {\mathbb R}$ . A bilinear Hilbert transform of Schwartz functions f and g is a function $z_{\alpha, \beta}(x) = \lim\limits_{\epsilon\to 0}\int\limits_{\frac{1}{\epsilon}>|t|>\epsilon} f(x-\alpha t)g(x-\beta t) \frac{dt}{t}$ , where $\alpha,\beta \in {\mathbb R}$ are real parameters.

The Theorem: On 2nd June 2000, Loukas Grafakos and Xiaochun Li submitted to Annals of Mathematics a paper in which they proved that for every $2 < p_1 < \infty$ , $2 < p_2 < \infty$ such that $1 < p = \frac{p_1p_2}{p_1+p_2} < 2$ , there is a constant $C = C(p_1, p_2)$ such that $\sup\limits_{\alpha, \beta} \|z_{\alpha, \beta}\|_p \leq C \|f\|_{p_1} \|g\|_{p_2}$ for all Schwartz functions $f, g: {\mathbb R}\to{\mathbb R}$ .

Short context: Bilinear Hilbert transform was introduced by Calderón in 1960, who also asked an important open question about it (which, however, too difficult to formulate it here). The Theorem, in combination with another result, resolves this 40-years old open question. The importance of the Theorem is that the constant C depends only on $p_1$ and $p_2$ , but not on $f,g,\alpha$ , and $\beta$ .

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

Go to the list of all theorems

Random polynomial of degree n has no real zeros with probability n^(-b+o(1))

You need to know: Polynomials, basic probability: random variables, distribution, independence, sequence of i.i.d. (independent identically distributed) random variables, expectation (or mean), variance. You also need $o(1)$ notation for context section.

Background: We say that random variable X possess finite moments of all orders if expectation of $|X|^k$ is finite for all $k>0$ . Let $a_0, a_1, a_2, \dots$ be a sequence of zero-mean, unit-variance, i.i.d. random variables possessing finite moments of all orders. Let $f_n(x)=\sum\limits_{i=0}^{n-1} a_i x^i$ , and let $P_n$ be the probability that $f_n(x) \neq 0, \,\, \forall x \in{\mathbb R}$ .

The Theorem: On 30th May 2000, Amir Dembo, Bjorn Poonen, Qi-Man Shao, and Ofer Zeitouni submitted to the Journal of the AMS a paper in which they proved that $\lim\limits_{n\to \infty}\frac{\log P_{2n+1}}{\log(2n+1)}=-b$ , where $b>0$ is a constant.

Short context: The study of real zeros of random polynomials has a long history, is mentioned by Waring in as early 1782, systematically studied by Littlewood and
Offord in 1938, and then by many others. In 1999, Poonen and Stoll, motivated by applications in arithmetic geometry, conjectured that $P_n=n^{-b+o(1)}$ for some $b>0$ . The Theorem confirms this prediction. The authors also prove that $0.4 \leq b \leq 2$ and predict that $b \approx 0.76 \pm 0.03$ .

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

Go to the list of all theorems