epsilon)

You need to know: Graph, isomorphic graphs, subgraph.

Background: A graph G is called H-free, if it does not have a subgraph isomorphic to H. Let $T:{\mathbb R}\to{\mathbb R}$ be a function defined by the rules (i) $T(1)=2$ , (ii) $T(n)=2^{T(n-1)}$ for $n=2,3,\dots$ , and (iii), for all real x, $T(x)=T(\bar{x})$ , where $\bar{x}$ is the least positive integer such that $x \leq \bar{x}$ .

The Theorem: On 10th January 2010, Jacob Fox submitted to the Annals of Mathematics a paper in which he proved the following result. For each $\epsilon>0$ and graph H on h vertices there is a $\delta=\delta(\epsilon,H)>0$ such that every graph on n vertices with at most $\delta n^h$ copies of H can be made H-free by removing at most $\epsilon n^2$ edges. Moreover, one can choose $\delta=T(5h^4\log \epsilon^{-1})^{-1}$ .

Short context: The statement of the Theorem without “moreover” part is famous graph removal lemma proved by Erdös, Frankl, and Rödl in 1986. It has many applications in graph theory and theory of algorithms. However, from their proof one can only take $\delta \approx T(P(\epsilon^{-1}))^{-1}$ for some polynomial P. The Theorem establishes the graph removal lemma with better dependence of $\delta$ from $\epsilon$ .

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

Go to the list of all theorems

Regular tetrahedra can be packed in R^3 with density 4000/4671=0.856347…

You need to know: Euclidean space ${\mathbb R}^3$ , volume in ${\mathbb R}^3$ , ball $B(O,r)\subset {\mathbb R}^3$ with center O and radius r, regular tetrahedron.

Background: By packing of regular tetrahedra in ${\mathbb R}^3$ we mean set E of (infinitely many) non-overlapping regular tetrahedra of the same size. For a point $O \in {\mathbb R}^3$ , denote $\delta(O,E) = \lim\limits_{r\to\infty}\frac{|B(O,r) \cap E|}{|B(O,r)|},$ where $|.|$ denotes volume in ${\mathbb R}^3$ . It can be shown that this limit, if exists, depends only on E but not on O and is called the density of E.

The Theorem: On 27th December 2009, Elizabeth Chen, Michael Engel, and Sharon Glotzer submitted to Discrete & Computational Geometry a paper in which they proved the existence of regular tetrahedra packing in ${\mathbb R}^3$ with density $\frac{4000}{4671}=0.856347\dots$ .

Short context: The problems of finding the densest possible packings of objects in the space are almost as old as mathematics. The densest packing of spheres was conjectured by Kepler in 1611 and confirmed only recently by Hales. For regular tetrahedra, the problem goes back at least to Aristotle, who mistakenly believed that perfect packing (that is, one that fully covers the space) is possible. In 2006, Conway and Torquato constructed a packing of regular tetrahedra with density about $0.72$ . In just few years after this, many author developed denser and denser packings, culminated in the Theorem, which provides the densest packing currently known.

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

Go to the list of all theorems

Principal component analysis with large but sparse noise can be done fast

You need to know: Euclidean space ${\mathbb R}^n$ , norm $||x||=\sqrt{\sum x_i^2}$ of $x=(x_1,\dots, x_n) \in {\mathbb R}^n$ , real matrix L (matrix with real entries $L_{ij}$ ), matrix multiplication, square matrix, l1 norm $||L||_1=\sum_{i,j}|L_{ij}|$ of matrix L, support set of L (set of pairs $(i,j)$ such that $L_{ij}\neq 0$ ), diagonal matrix D, identity matrix I, transpose $L^T$ of matrix L, orthonormal matrix (such that $L^TL=LL^T=I$ ) singular value decomposition of a square matrix L (writing $L=UDV^T$ where D is the diagonal matrix and $U,V$ are orthonormal matrices), rank of the matrix L (the number of non-zero entries of D), nuclear norm $||L||_*$ of L (sum of all entries of D).

Background: Let $\mu>0$ be a fixed real number. Let $e_i \in {\mathbb R}^n$ be a vector with $i$ -th component $1$ and others $0$ . Let $L_0$ be a real $n \times n$ matrix of rank r whose singular value decomposition $L_0=UDV^T$ satisfies (i) $\max_i ||U^Te_i||\leq \frac{\mu r}{n}$ , (ii) $\max_i ||V^Te_i||\leq \frac{\mu r}{n}$ , and (iii) $\max_{i,j}|w_{ij}|\leq \frac{\sqrt{\mu r}}{n}$ , where $w_{ij}$ are entries of matrix $UV^T$ . Let $\Sigma$ be a fixed $n\times n$ matrix with $\pm 1$ entries $\Sigma_{ij}$ . Choose integer $0<m<n^2$ . Let $S_0$ be $n\times n$ matrix with entries $[S_0]_{ij}$ whose support set $\Omega$ is uniformly distributed among all sets of cardinality m, and such that the sign of $[S_0]_{ij}$ is $\Sigma_{ij}$ for all $(i,j)\in \Omega$ . Let $M=L_0+S_0$ . Let $\hat{L}$ , $\hat{S}$ be the solution to optimization problem $\min\limits_{L,S}(||L||_*+\frac{1}{\sqrt{n}}||S||_1)$ subject to $L+S=M$ .

The Theorem: On 18th December 2009, Emmanuel Candes, Xiaodong Li, Yi Ma, and John Wright submitted to arxiv a paper in which they proved the following result. Suppose that $L_0$ and $S_0$ are as above. Then, there are positive constants $c$ , $c_r$ , $c_s$ such that with probability at least $1-cn^{-10}$ (over the choice of support of $S_0$ ), we have $\hat{L}=L_0$ and $\hat{S}=S_0$ provided that $\text{rank}(L_0) \leq c_r n \mu^{-1}(\log n)^{-2}$ and $m \leq c_s n^2$ .

Short context: Many real life data has the form of matrix $M=L_0+S_0$ , where $L_0$ is a low-rank matrix and $S_0$ is some perturbation. A fundamental problem, known as “principal component analysis” is to recover $L_0$ from M. Most known method works if $S_0$ is small, but this assumption often fails in applications. The Theorem states that $L_0$ can be efficiently recovered if $S_0$ is sparse, that is, has not too many non-zero entries (which, however, can be arbitrary large!). Conditions (i)-(iii) for $L_0$ are needed to ensure that $L_0$ is not sparse. The Theorem can be extended to rectangular matrices $L_0, S_0$ as well.

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

Go to the list of all theorems

When n>=5, the Dehn function of SL(n;Z) is quadratic

You need to know: Notation ${\mathbb Z}$ for the set of integers, ${\mathbb N}$ for the set of positive integers, matrix, determinant of a matrix, group, group $SL(n;{\mathbb Z})$ of $n\times n$ matrices with integer entries and determinant 1, presentation of a group in the form $<S|R>$ where S is a set of generators and R is a set of relations, finitely presented group.

Background: For functions $f; g : {\mathbb N} \to {\mathbb N}$ , we write $g \succeq f$ if there is a c such that $f(n) \leq cg(cn + c) + c$ for all n, and $f \sim g$ if $g \succeq f$ and $g \succeq f$ . A word in a finitely presented group G is any product of generators and their inverse elements. For any word w representing the identity element e, there is a sequence of steps that reduces w to the empty word, where each step is a free reduction or insertion or the application of a relator. We call the number of applications of relators in a sequence its cost, and let T(w) be the minimum cost of a sequence that transforms w into e. The Dehn function is $\delta_G(n) =\max\limits_{w:l(w)\leq n} T(w)$ , where the maximum is taken over words of length at most n representing the identity. We say that the Dehn function is quadratic if $\delta_G(n) \sim n^2$ . This property depends only on G but not on set of generators.

The Theorem: On 14th December 2009, Robert Young submitted to arxiv a paper in which he proved that, for any $n\geq 5$ , the Dehn function of $SL(n;{\mathbb Z})$ is quadratic.

Short context: The growth rate of the Dehn function is a fundamental invariant of a finitely presented group, which connects group theory, theory of algorithms, and geometry. For $SL(n;{\mathbb Z})$ , the Dehn function grows linearly for $n=2$ , and exponentially fast for $n=3$ . For $n\geq 4$ , Thurston conjectured that it grows quadratically. The Theorem confirms this conjecture for $n\geq 5$ .

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

Go to the list of all theorems

For d>=19, the one-arm exponent for critical bond percolation in Z^d is 1/2

You need to know: Set ${\mathbb Z}^d$ of vectors $x=(x_1,\dots, x_d)$ with integer components, $||x||=\sqrt{\sum_{i=1}^d x_i^2}$ , origin $O=(0,0,\dots,0)\in {\mathbb Z}^d$ , graph, path in a graph, infinite graph, probability, independence.

Background: Let G be an infinite graph with vertex set ${\mathbb Z}^d$ such that $x,y \in{\mathbb Z}^d$ are connected by an edge if and only if $||x-y||=1$ . Given $p\in[0,1]$ , a bond percolation $G_p$ in ${\mathbb Z}^d$ is a subgraph of G to which each edge of G is included independently with probability p. Given $r>0$ , let $P_d(p,r)$ be the probability that there exists a path in $G_p$ from origin O to some vertex $x \in {\mathbb Z}^d$ with $||x||>r$ . It is known that for every $d\geq 2$ there exists a $p_d \in [0,1]$ such that $L_d(p)=\lim\limits_{r\to \infty}P_d(p,r)=0$ for $p<p_d$ but $L_d(p)=1$ for $p>p_d$ .

The Theorem: On 4th November 2009, Gady Kozma and Asaf Nachmias submitted to arxiv and the Journal of the AMS a paper in which they proved that $P_d(p_d,r) \approx r^{-2}$ for every $d\geq 19$ , where $f(r) \approx g(r)$ means that $C^{-1}f(r) \leq g(r) \leq Cf(r)$ for some constant $C>0$ which might depend on d but not on r.

Short context: The study of percolations is motivated by physical applications and mathematical beauty, and is especially challenging for $p=p_d$ . It is believed that $L_d(p_d)=0$ for all $d\geq 2$ , and this is considered to be one of the most challenging open problems in probability theory. Intuition from physics suggest that not only $L_d(p_d)=0$ , but in fact $P_d(p_d,r) \approx r^{-1/\rho}$ for some $\rho=\rho(d)>0$ , which is called the one-arm exponent for critical bond percolation in ${\mathbb Z}^d$ . The Theorem proved that for all $d\geq 19$ this one-arm exponent indeed exists and is equal to $1/2$ .

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

Go to the list of all theorems

The density Hales-Jewett theorem holds with an explicit bound

You need to know: Let ${\mathbb N}$ be the set of positive integers $\{1,2,3,\dots\}$ , big O notation.

Background: For positive integers k,n, let $[k]=\{1,2,\dots,k\}$ and let $[k]^n$ be the set of vectors $x=(x_1, \dots, x_n)$ such that each $x_i\in[k]$ . Let $y=(y_1, \dots, y_n)$ be a vector such that each $y_i$ either belongs to $[k]$ or equal to the wildcard value *. Assume that at least one coordinate of y takes the wildcard value *. For $j=1,2,\dots, k$ , let $y^j \in [k]^n$ be a vector obtained from y by setting all the wildcards * equal to j. The set $y^1, y^2, \dots, y^n$ is called a combinatorial line. Let $A:{\mathbb N} \times {\mathbb N} \to {\mathbb N}$ be a function such that $A(k,1)=2$ for all k, $A(1,n)=2n$ for all n, and $A(k,n) = A(k-1, A(k,n-1))$ for all $k, n>1$ .

The Theorem: On 20th October 2009, a large group of mathematicians submitted to arxiv a paper in which they proved the following result. For every positive integer k and every real number $\delta>0$ , there exists a positive integer $N=N(k,\delta)$ such that if $n\geq N$ and A is any subset of $[k]^n$ with at least $\delta k^n$ elements, then A contains a combinatorial line. Moreover, one may take $N(3,\delta) = A(3,O(1/\delta^2))$ and $N(k, \delta) = A(k+1,O(1/\delta))$ for $k \geq 4$ .

Short context: In 1975, Szemerédi proved that for any $k\in {\mathbb N}$ and any $\delta > 0$ , there exists a positive integer $M = M(k, \delta)$ such that every subset of the set $\{1, 2, \dots ,M\}$ of size at least $\delta M$ contains an arithmetic progression of length k. In 1991, Furstenberg and Katznelson proved the statement of the Theorem without “moreover” part, and called it “the density Hales-Jewett theorem”. This theorem greatly generalises (and easily implies) the Szemerédi theorem. However, the proof of Furstenberg and Katznelson does not imply any explicit algorithm how to actually compute $N=N(k,\delta)$ given $k$ and $\delta$ . The Theorem provides such an algorithm. It also has much simpler proof. It is proved by a large group of mathematicians in an online discussion, which is called a Polymath project.

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

Go to the list of all theorems

The threshold conjecture of Turán properties for random graphs is true

You need to know: Graph, notation $K_n$ for complete graph on n vertices, notations $v(H)$ and $e(H)$ for the number of vertices and edges in graph H, respectively.

Background: For a graph $F$ with $e(F)\geq 1$ and $v(F)\geq 3$ , let $m(F)$ be the maximum value of $\frac{e(H)-1}{v(H)-2}$ over all subgraphs H of F with $v(H)\geq 3$ . We say that a graph is F-free if it does not contain a copy of a graph F as a subgraph. For graph G, we write $\text{ex}(G, F)$ for the maximal number of edges that an F-free subgraph of G may have. Number $\pi(F)=\lim\limits_{n\to\infty}\frac{ex(K_n,F)}{e(K_n)}$ is known as Turán density of graph F. The Erdős-Renyi graph $G(n,p)$ is a random graph with n vertices, such that every possible edge is included independently with probability $p=p(n)$ .

The Theorem: On 16th October 2009, Mathias Schacht submitted to the Annals of Mathematics a paper in which he proved that for every graph $F$ with $e(F)\geq 1$ and $v(F)\geq 3$ and every $\epsilon>0$ , there exists $C=C(\epsilon)>0$ such that for every sequence of probabilities $q_n \geq Cn^{-1/m(F)}$ , we have $\lim\limits_{n\to\infty} P\left[\text{ex}(G(n,q_n),F) \leq \left(\pi(F)+\epsilon\right)e(G(n,q_n))\right]=1$ .

Short context: Function $\text{ex}(G, F)$ was first studied by Mantel, Erdős, and Turán. In particular, Turán determined in 1941 $\text{ex}(K_n, K_k)$ for all integers n and k. For general graph G, it is known that $\text{ex}(G, F) \geq \pi(F)e(G)$ . The Theorem proves that if G is a random graph, then the opposite inequality $\text{ex}(G, F) \leq (\pi(F)+\epsilon)e(G)$ holds with high probability. It confirms a conjecture of Kohayakawa, Łuczak, and Roedl made in 1997.

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

Go to the list of all theorems

The Furstenberg’s conjecture on dimension of sum of invariant sets in true

You need to know: Closed subset of $[0,1]$ , multiplication of a set by a constant $s\cdot A = \{s\cdot a: a \in A\}$ , sum of two sets $A + B = \{a + b : a \in A; b \in B\}$ , Hausdorff dimension $\text{dim}(A)$ of set $A \subset [0,1]$ .

Background: For real number $x$ , let $\left \lfloor{x}\right \rfloor$ be the largest integer not exceeding x, and let $\text{frac}(x)=x-\left \lfloor{x}\right \rfloor$ . For integer m, let $T_m:[0,1)\to[0,1)$ be a function given by $T_m(x)=\text{frac}(mx)$ . We say that set $S \subset [0,1]$ is invariant under $T_m$ if $T_m(x) \in S$ for every $x \in S$ .

The Theorem: On 11th October 2009, Michael Hochman and Pablo Shmerkin submitted to arxiv a paper in which they proved the following result. Let $X; Y \subseteq [0,1]$ be closed sets which are invariant under $T_2$ and $T_3$ , respectively. Then, for any $s \neq 0$ , $\text{dim}(X + s\cdot Y ) = \min\{1, \text{dim} X + \text{dim} Y\}$ .

Short context: The Theorem confirms a long-standing conjecture of Furstenberg made in late 1960th. See here for a theorem resolving another related conjecture of Furstenberg in a later work.

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

Go to the list of all theorems

The critical bias for the Hamiltonicity Maker-Breaker game is (1+o(1))n/log n

You need to know: Graph, complete graph, Hamilton cycle in a graph, logarithm $\log$ , small o notation.

Background: In the biased (1 : b) Hamiltonicity Maker-Breaker game, the players, called Maker and Breaker, take turns in claiming unoccupied edges of complete graph $K_n$ on n vertices. Maker claims 1 edge in his turn, Breaker answers by claiming b edges. Maker wins if she can construct a Hamilton cycle from the edges she have chosen.

The Theorem: On 15th September 2009, Michael Krivelevich submitted to arxiv a paper in which he proved that Maker has a strategy to win the (1 : b) Hamiltonicity game on $K_n$ in at most $14n$ moves, for every $b \leq \left(1-\frac{30}{\log^{1/4}n}\right)\frac{n}{\log n}$ , for all large enough n.

Short context: The research on biased Hamiltonicity games has a long history, starting from 1978 paper of Chvátal and Erdös, who showed that the Maker wins for large n if $b=1$ (in 2009, Hefetz and Stich proved that Maker can win in just n+1 rounds, which is optimal). In general, the critical bias $b^*(n)$ is the maximum possible value of b for which Maker still wins the (1 : b) game played on $K_n$ . Chvátal and Erdös proved that $b^*(n) \leq \left(1+o(1)\right)\frac{n}{\log n}$ . Many authors proved better and better lower bounds, culminating in the Theorem which implies that $b^*(n) \geq \left(1+o(1)\right)\frac{n}{\log n}$ , and hence equality holds.

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

Go to the list of all theorems

Systems of polynomial equations can be solved in average time N^O(log log N)

You need to know: Complex numbers, polynomials in complex variable, notation ${\mathbb C}^n$ for set of vectors $z=(z_1, \dots, z_n)$ with complex $z_i$ , algorithm, probabilistic and deterministic algorithms, average running time of an algorithm, big O notation.

Background: Let $n>0$ be a positive integer. Let H be the space of all systems $f = [f_1,\dots ,f_n]:{\mathbb C}^n \to {\mathbb C}^n$ on n polynomial equations in n unknowns. For $f \in H$ , denote $V_{\mathbb C}(f) = \{x \in {\mathbb C}^n : f_i(x) = 0, \, 1 \leq i \leq n\} \subset {\mathbb C}^n$ the set of solutions of $f$ .

The Theorem: On 11th September 2009, Peter Buergisser and Felipe Cucker submitted to arxiv a paper in which they described an explicit deterministic algorithm that computes an approximate solution of any given $f \in H$ with any given accuracy, and proved that the average number of arithmetic operations of this algorithm is $N^{O(\log\log N)}$ , where N is the size of the input.

Short context: Solving polynomial equations and systems of such equations is one of the fundamental problems in the whole mathematics. In 1998, Smale presented a list of problems he considered as the most important ones for the 21st century. Smales 17th problem asks for the (deterministic) algorithm which could solve systems of polynomial equations with polynomial average running time. In an earlier work, Beltrán and Pardo developed a probabilistic algorithm which achieves this. The Theorem provides a deterministic algorithm with nearly polynomials average running time $N^{O(\log\log N)}$ . In later works, Lairez developed deterministic algorithm with polynomial average time, and also a probabilistic algorithm with quasilinear running time $N^{1+o(1)}$ , see here.

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

Go to the list of all theorems