The Alon-Yuster conjecture on factors in random graphs is true

You need to know: Graph, vertices, edges, notation $v(H)$ and $e(H)$ for the number of vertices and edges in graph H, subgraph, limits, basic probability theory, independent events.

Background: For a graph H on at least two vertices, let $d^*(H) =\max\limits_{H'\subseteq H}\frac{e(H')}{v(H')-1}$ . The Erdos-Renyi graph G with edge density $p=p(n)$ is a random graph with n vertices, such that every possible edge is included independently with probability p.

The Theorem: On 11th October 2007, August Johansson, Jeff Kahn, and Van Vu submitted to Random Structures & Algorithms a paper in which they proved that, for any graph H on at least two vertices, and any $\epsilon>0$ , the probability that Erdos-Renyi random graph with $n=k v(H)$ vertices and edge density $p=n^{-\frac{1}{d^*(H)}+\epsilon}$ can be partitioned on $k$ subgraphs isomorphic to $H$ , tends to $1$ as $k \to \infty$ .

Short context: If vertices of a graph G can be partitioned into disjoint copies of graph H, we say that G has an H-factor. A natural and well-studied question is for what minimal edge density p the random graph G has an H-factor with high probability. The Theorem answers this question, confirming a conjecture of Alon and Yuster made in 1993. The result is the best possible up to $\epsilon$ term.

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

Go to the list of all theorems

The Hausdorff dimension of the set of singular pairs is 4/3

You need to know: Euclidean space ${\mathbb R}^2$ , norm $||{\bf x}||=\sqrt{x_1^2+x_2^2}$ of vector ${\bf x}=(x_1, x_2) \in {\mathbb R}^2$ , Hausdorff dimension of a subset of ${\mathbb R}^2$ .

Background: Vector ${\bf x}=(x_1, x_2) \in {\mathbb R}^2$ is called singular pair if for every $\delta > 0$ there exists $T_0$ such that for all $T>T_0$ there exist vector ${\bf p}=(p_1, p_2)$ with integer coordinates and integer $q$ , $0<q<T$ , such that $||q{\bf x}-{\bf p}||<\frac{\delta}{\sqrt{T}}$ .

The Theorem: On 27th September 2007, Yitwah Cheung submitted to the Annals of Mathematics a paper in which they proved that the set of all singular pairs in ${\mathbb R}^2$ has Hausdorff dimension $\frac{4}{3}$ .

Short context: Singular pair is a pair of real numbers $(x_1,x_2)$ that can be simultaneously approximated by rational numbers $\frac{p_1}{q}, \frac{p_2}{q}$ with the same not too large denominator, see here for a progress in a related Littlewood conjecture. All points on any line $a_1x_1+a_2x_2+b=0$ with rational coefficients $a_1, a_2, b$ are known to be singular pairs. The set of points on such lines has Hausdorff dimension $1$ . The Theorem shows that the set of all singular pairs is much large.

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

Go to the list of all theorems

Every triangle with all angles at most 100 degrees has a periodic billiard path

You need to know: Polygon, angles measured in radians, angle of incidence, angle of reflection, limits, Hausdorff dimension of a set.

Background: A billiard path in a triangle T is a point moving inside T with constant speed, with the usual rule that the angle of incidence equals the angle of reflection. Such a path is fully described by point’s initial position and initial direction to move. A billiard path is called periodic if, at some time moment, the point trajectory starts to repeat itself.

The Theorem: On 8th September 2007, Richard Evan Schwartz submitted to the Experimental mathematics a paper in which he proved that every triangle with all angles at most one hundred degrees has a periodic billiard path.

Short context: Billiard path is a simple but fundamental example of a dynamical system. More that two-hundred-year-old triangular billiards conjecture predicts that every triangle has a periodic billiard path. The conjecture is relatively easy for rational triangles (those whose angles are all rational multiples of $\pi$ ), and also for right triangles. In 1775, Fagnano proved it for acute triangles. However, there was essentially no progress for general (possibly not rational) obtuse triangles. The Theorem proves the conjecture for all triangles with largest angle at most 100 degrees.

Links: The original paper is available here.

Go to the list of all theorems

Upper and lower bounds for the number of squarefree d (0 < d < X) such that the equation x^2-dy^2=-1 is solvable

You need to know: Limit $\lim$ , limit inferior $\liminf$ , limit superior $\limsup$ , infinite product $\prod\limits_{j=1}^{\infty}f(j)$ .

Background: For positive functions $g(X)$ and $h(X)$ we write $g(X)\sim h(X)$ if $\lim\limits_{X\to\infty}\frac{g(X)}{h(X)}=1$ , $g(X)=o(h(X))$ if $\lim\limits_{X\to\infty}\frac{g(X)}{h(X)}=0$ , and $g(X)=\Theta(h(X))$ if $0<\liminf\limits_{X\to\infty}\frac{g(X)}{h(X)} \leq \limsup\limits_{X\to\infty}\frac{g(X)}{h(X)}<\infty$ . An integer d is called squarefree if it is divisible by no perfect square other than 1. For any $X>0$ , let $f(X)$ be the number of positive squarefree integers d less than X such that equation $x^2-dy^2=-1$ has a solution in integers $x,y$ . Also, let us define constants $\alpha=\prod\limits_{j=1}^{\infty}(1+2^{-j})^{-1}=0.419...$ and $\beta=\frac{3}{2\pi}\prod\limits_{p\in{\cal P}_1}\sqrt{1-p^{-2}}$ , where ${\cal P}_1$ denotes the set of all prime numbers p such that $p-1$ is divisible by 4.

The Theorem: On 5th July 2007, Étienne Fouvry and Jürgen Klüners submitted to the Annals of Mathematics a paper in which they proved the existence of positive constants $C_1, C_2$ such that $(C_1-o(1))\left(\frac{X}{\sqrt{\log X}}\right) \leq f(X)\leq (C_2+o(1))\left(\frac{X}{\sqrt{\log X}}\right)$ . In fact, they proved this for $C_1=\alpha \cdot \beta$ and $C_2=\frac{2}{3}\beta$ .

Short context: For integer $d>0$ , fraction $\frac{x}{y}$ approximates $\sqrt{d}$ from below if $x^2-dy^2<0$ , and the approximation is best if $x^2-dy^2=-1$ . This is called the negative Pell equation. For how many squarefree d it is solvable? In 1993, Stevenhagen conjectured that $f(X) \sim (1-\alpha)\beta\left(\frac{X}{\sqrt{\log X}}\right)$ . The Theorem proves that $f(X)=\Theta\left(\frac{X}{\sqrt{\log X}}\right)$ with constants $(0.419...)\beta$ and $(0.666...)\beta$ for the lower and upper bounds, respectively. In a later work, Fouvry and Klüners improved the lower bound to $\frac{5\alpha}{4}\beta=(0.524...)\beta$ . This is close to the conjectured constant $(1-\alpha)\beta\approx 0.58\beta$ .

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

Go to the list of all theorems

If a finite subset A of a free group has non-commuting elements, then |A^3|>|A|^2/(log|A|)^O(1)

You need to know: Group, free group, notation $|A|$ for the number of elements in a finite set A, $O(1)$ and $o(1)$ notations.

Background: For subsets A and B of group G denote $A \cdot B=\{g\in G \,|\,g=ab, \, a\in A, \, b \in B\}$ . Denote $A^3 = A \cdot A \cdot A$ .

The Theorem: On 18th June 2007, Alexander Razborov submitted to the Annals of Mathematics a paper in which he proved that, if A is a finite subset of a free group $F_m$ with at least two noncommuting elements, then $|A^3| \geq \frac{|A|^2}{(\log|A|)^{O(1)}}$ .

Short context: For sets of integers A,B, let $A+B=\{a+b \,|\, a\in A, \, b \in B\}$ . If A is an arithmetic progression, then $|A+A|<2|A|$ . A deep 1973 theorem of Freiman describes all possible examples of sets A such that $|A+A|\leq k|A|$ for fixed k. For many applications, it is important to derive the structure of A from a weaker estimate of the form $|A+A|\leq |A|^{1+o(1)}$ , but this is open. For subsets A of arbitrary group G, it is impossible to deduce the structure of A is $|A^2|$ is small, but sometimes possible if $|A^3|$ is small. The Theorem implies that in free groups $|A^3|$ is small only if $ab=ba$ for all $a,b \in A$ .

Links: The original paper is available here.

Go to the list of all theorems

Nonlinear complex same-degree polynomials with infinite orbit intersection must have a common iterate

You need to know: Complex numbers, set ${\mathbb C}[X]$ of polynomials $f(x)$ in complex variable $x$ with complex coefficients, degree $\text{deg}(f)$ of a polynomial f, notation $f^n(z)$ for $f(f(\dots f(z)\dots))$ , where f is repeated n times.

Background: For $f \in {\mathbb C}[X]$ , and initial point $x_0 \in {\mathbb C}$ , the orbit $O_f(x_0)$ is the set $\{x_0, f(x_0), f(f(x_0)), \dots, f^n(x_0), \dots\}$ . We say that same degree polynomials $f, g \in {\mathbb C}[X]$ have a common iterate if latex $f^n = g^n$ for some n.

The Theorem: On 14th May 2007, Dragos Ghioca, Thomas Tucker, and Michael Zieve submitted to arxiv a paper in which they proved the following result. Let $x_0, y_0 \in {\mathbb C}$ and $f, g \in {\mathbb C}[X]$ with $\text{deg}(f) = \text{deg}(g) > 1$ . If $O_f(x_0) \cap O_g(y_0)$ is infinite, then f and g have a common iterate.

Short context: The study of orbits of polynomial maps is one of the main topics in complex dynamics. One natural question to ask is under what conditions two orbits may have infinite intersections. This may obviously be the case if the polynomials have the common iterate. The Theorem states that, for same-degree non-linear polynomials, this obvious sufficient condition is in fact necessary. The Theorem has applications in arithmetic geometry.

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

Go to the list of all theorems

Any order-reversing involution on convex functions is, up to linear terms, Legendre transform

You need to know: Euclidean space ${\mathbb R}^n$ , scalar product $\langle x,y \rangle=\sum\limits_{i=1}^n x_iy_i$ in ${\mathbb R}^n$ , extended real line $\bar{\mathbb R} = {\mathbb R}\cup\{\pm \infty\}$ , convex function $\phi: {\mathbb R}^n \to \bar{\mathbb R}$ , lower-semi-continuous function $\phi: {\mathbb R}^n \to \bar{\mathbb R}$ , supremum.

Background: A map $B:{\mathbb R}^n \to {\mathbb R}^n$ is called linear if $B(x+y)=B(x)+B(y)$ and $B(\alpha x)=\alpha B(x)$ for all $x,y \in {\mathbb R}^n$ and $\alpha\in{\mathbb R}$ , symmetric if $\langle Ax,y \rangle = \langle x,Ay \rangle$ for all $x,y \in {\mathbb R}^n$ , and invertible if $B(x)\neq 0$ whenever $x \neq 0$ . Let ${\cal C}({\mathbb R}^n)$ denote the set of all lower-semi-continuous convex functions $\phi: {\mathbb R}^n \to \bar{\mathbb R}$ . Map ${\cal L}:{\cal C}({\mathbb R}^n) \to {\cal C}({\mathbb R}^n)$ given by $({\cal L}\phi)(x) = \sup\limits_{y \in {\mathbb R}^n}(\langle x,y \rangle -\phi(y))$ is called the Legendre transform.

The Theorem: On 1st May 2007, Shiri Artstein-Avidan and Vitali Milman submitted to the Annals of Mathematics a paper in which they proved that for every map $T :{\cal C}({\mathbb R}^n) \to {\cal C}({\mathbb R}^n)$ (defined on the whole domain ${\cal C}({\mathbb R}^n)$ ) satisfying (P1) $TTf=f$ and (P2) $f \leq g$ implies $Tf \geq Tg$ , there exists a constant $C_0 \in {\mathbb R}$ , a vector $v_0\in {\mathbb R}^n$ , and an invertible symmetric linear map B such that $(T f)(x) = ({\cal L}f)(Bx+v_0) + \langle x, v_0 \rangle + C_0$ for all $x \in {\mathbb R}^n$ .

Short context: The Legendre transform is a central tool in convex analysis and optimisation, with numerous applications. Map $T$ satisfying properties (P1) and (P2) in the Theorem is called an order-reversing involution. Is it easy to check that the Legendre transform satisfies these properties. The Theorem states a somewhat surprising converse: any order-reversing involution must in fact be the Legendre transform, up to linear terms.

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

Go to the list of all theorems

Entire function whose escaping set has only bounded path-components

You need to know: Set ${\mathbb C}$ of complex numbers, absolute value $|z|$ of $z\in{\mathbb C}$ , limits, function $f(z)$ in complex variable z, its derivative $f'(z)$ , polynomials, notation $f^n(z)$ for $f(f(...f(z)...))$ where f is applied n times, bounded subsets of ${\mathbb C}$ , path (or curve) connecting points $x \in {\mathbb C}$ and $y \in {\mathbb C}$ .

Background: A function $f:{\mathbb C}\to {\mathbb C}$ is called entire if $f'(z)$ exists for all $z\in {\mathbb C}$ . An entire function f is called transcendental if it is not a polynomial. An escaping set of a transcendental entire function f is the set $I(f)=\{z\in {\mathbb C} : \lim\limits_{n\to\infty}|f^n(z)|=\infty\}$ . A path-component of $I(f)$ is the set of all $y\in I(f)$ which can be connected by a path $P \subset I(f)$ to any fixed $x\in I(f)$ .

The Theorem: On 24th April 2007, Günter Rottenfusser, Johannes Rückert, Lasse Rempe, and Dierk Schleicher submitted to arxiv a paper in which they proved the existence of a transcendental entire function f whose escaping set $I(f)$ has only bounded path-components.

Short context: The study of limiting behaviour of sequence $f^n(z)$ for transcendental entire function f goes back to 1926 paper of Fatou. This is an example of dynamical system. In 1989, Eremenko, formalising a question of Fatou, asked whether the escaping set $I(f)$ of any transcendental entire function f has the property that every point $z\in I(f)$ can be joined with $\infty$ by a curve in $I(f)$ . The Theorem answers this question in negative.

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

Go to the list of all theorems

The problem of computing a two-player Nash equilibrium is PPAD-complete

You need to know: Vectors, matrices, transpose $x^T$ of vector x, matrix multiplication, algorithms and their running times, polynomial algorithm, polynomial-time reduction, complexity classes P and PPAD (Polynomial Parity Arguments on Directed graphs), PPAD-complete problem.

Background: Let ${\mathbb P}^n$ be the set of vectors $x=(x_1,\dots,x_n)\in{\mathbb R}^n$ such that all $x_i \geq 0$ and $\sum\limits_{i=1}^n x_i = 1$ . The problem of computing a two-player Nash equilibrium is: given two $m\times n$ matrices A and B with rational entries, compute vectors $x^* \in {\mathbb P}^m$ and $y^* \in {\mathbb P}^n$ such that $(x^*)^TAy^* \geq x^TAy^*$ and $(x^*)^TBy^* \geq (x^*)^TBy$ for all $x\in {\mathbb P}^m$ and $y\in {\mathbb P}^n$ .

The Theorem: On 12th April 2007, Xi Chen, Xiaotie Deng, and Shang-Hua Teng submitted to arxiv a paper in which they proved that the problem of computing a two-player Nash equilibrium is PPAD-complete.

Short context: The problem of computing a two-player Nash equilibrium is a fundamental problem in game theory with applications to, for example, economics. Famous theorem of Nash from 1950 implies that Nash equilibrium exists for any matrices A and B. However, it was an open question if there is a polynomial-time algorithm for computing it. The Theorem implies that such algorithm does not exist, unless a well-believed conjecture P $\neq$ PPAD fails.

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

Go to the list of all theorems

The norm of the inverse of n by n matrix with i.i.d. subgaussian entries is at most n^0.5/e with probability 1-Ce-c^n

You need to know: Probability (denoted by P), mean, variance, fourth moment, abbreviation i.i.d. for independent identically distributed random variables, Euclidean space ${\mathbb R}^n$ , notation $|x|$ for length of $x \in {\mathbb R}^n$ , matrix, matrix multiplication, norm $||A||=\sup\limits_{x \in {\mathbb R}^n}\frac{|Ax|}{|x|}$ of $n \times n$ matrix A, inverse matrix $A^{-1}$ .

Background: For integer $n>0$ , let $A_{n,X}$ be an $n \times n$ matrix whose entries $a_{ij}$ are i.i.d. with the same distribution as X. A random variable X is called subgaussian if there exists constant B such that $P(|X|>t) \leq 2e^{-t^2/B^2}$ for all $t>0$ . The minimal B such that this holds is called the subgaussian moment of X. We will assume convention $\|A_{n,X}^{-1}\| = \infty$ if $A_{n,X}^{-1}$ does not exist.

The Theorem: On 16th March 2007, Mark Rudelson and Roman Vershynin submitted to arxiv a paper in which they proved that for any $B>0$ there exist constants $C=C(B)>0$ and $c=c(B)\in(0,1)$ such that for any subgaussian random variable X with mean $0$ , variance $1$ , and subgaussian moment at most B, any integer $n>0$ , and any $\epsilon \geq 0$ , the probability that $\|A_{n,X}^{-1}\| \geq \sqrt{n}/\epsilon$ is at most $C\epsilon+c^n$ .

Short context: In 1963, von Neumann predicted that $\|A_{n,X}^{-1}\|$ is proportional to $\sqrt{n}$ for random matrices with high probability. Before 2007, this was open even if $X$ takes values $\pm 1$ with equal chances (in which case $A_{n,X}$ is called Bernoulli matrix). For Bernoulli matrices, Spielman and Teng made in 2002 a stronger conjecture that $P(\|A_{n,X}^{-1}\| \geq \sqrt{n}/\epsilon) \leq C\epsilon+c^n$ . The Theorem proves this conjecture for all matrices with i.i.d. subgaussian entries. Earlier, it was only known that $P(\|A_{n,X}^{-1}\| \geq n^{3/2}/\epsilon)$ is small. Also, the special $B=C+\frac{1}{2}$ case of the Theorem implies this previous result of Tao and Vu. In addition, Rudelson and Vershynin confirmed the von Neumann prediction assuming only that fourth moment of X is bounded.