The diagonal Ramsey numbers r(k+1,k+1) do not exceed C_m 4^k/k^m

You need to know: Graph, complete graph, binomial coefficient ${n\choose k}=\frac{n!}{k!(n-k)!}$ .

Background: Let $K_n$ denote the complete graph with n vertices. The (two-colour) Ramsey number $r(k, l)$ is the smallest natural number n such that, in any red and blue colouring of the edges of $K_n$ , we are guaranteed to find either a red $K_n$ or a blue $K_l$ . The Ramsey numbers $r(k, k)$ are called diagonal.

The Theorem: On 11th July 2006, David Conlon submitted to the Annals of Mathematics a paper in which he proved the existence of a constant $C>0$ such that inequality $r(k+1,k+1) \leq k^{-C\frac{\log k}{\log \log k}}{2k\choose k}$ holds for all integers $k \geq 2$ .

Short context: In 1929, Ramsey proved that for any positive integers $k,l$ exists n such that any red-blue edge colouring of $K_n$ contains either red $K_n$ or a blue $K_l$ . This implies that numbers $r(k, l)$ exist and finite. In 1935, Erdős and Szekeres proved that $r(k+1,l+1) \leq {k+l\choose k}$ . In particular, $r(k+1,k+1) \leq {2k\choose k}$ . In 1988, Thomason improved it to $r(k+1,k+1) \leq k^{-1/2+A/\sqrt{\log k}}{2k\choose k}$ . The Theorem is a major improvement of the Thomason’s bound. In particular, it implies that for any $m>0$ there is a constant $C_m>0$ such that $r(k+1,k+1) \leq C_m\frac{4^k}{k^m}$ for all k.

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

Go to the list of all theorems

Menger’s theorem holds for infinite digraphs

You need to know: Graph, bipartite graph, directed graph (digraph), infinite digraph, path in a digraph.

Background: Let A and B be two sets of vertices in a possibly infinite digraph G. A path from some $a\in A$ to some $b\in B$ will be called A–B-path. We say that set S of vertices of G separates A from B if every A–B-path contains at least one vertex $s \in S$ .

The Theorem: On 18th September 2005, Ron Aharoni and Eli Berger submitted to arxiv a paper in which they proved that, given two sets of vertices, A and B, in a (possibly infinite) digraph, there exists a family P of disjoint A–B-paths, and a set S separating A from B, such that S consists of a choice of precisely one vertex from each path in P.

Short context: For any two sets A and B in a finite digraph G, let $\sigma(A,B)$ be the minimal size of set S which separates A from B, and let $\nu(A,B)$ be the maximal size of a family of vertex-disjoint paths from A to B. Obviously, $\sigma(A,B) \geq \nu(A,B)$ . In 1931, König proved that equality $\sigma(A,B) = \nu(A,B)$ holds for every finite bipartite graph G. By an earlier 1927 theorem of Menger, this implies that $\sigma(A,B) = \nu(A,B)$ in every finite digraph G (not necessary bipartite). This implies the existence of a family of disjoint paths and separating set with the one-to-one correspondence. In 1936, Erdős conjectured that the same remains true for infinite digraphs. The Theorem proves this conjecture.

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

Go to the list of all theorems

The edge-deletion problem can be approximated in linear time

You need to know: Basic graph theory, bipartite graph, deterministic algorithm, approximation algorithm, running time of an algorithm, NP-hard problem, big O notation.

Background: A graph property is monotone if it is closed under removal of vertices and edges. The edge-deletion problem is: given a monotone property P and a graph G, compute the smallest number $E_P(G)$ of edge deletions that are needed in order to turn G into a graph satisfying P.

The Theorem: On 7th July 2005, Noga Alon, Asaf Shapira, and Benny Sudakov submitted to the Annals of Mathematics a paper in which they proved the following result. For any fixed $\epsilon>0$ and any monotone property P, there is a deterministic algorithm which, given a graph G with n vertices and m edges, approximates $E_P(G)$ in linear time $O(n+m)$ to within an additive error of $\epsilon n^2$ . On the other hand, if all bipartite graphs satisfy P, then for any fixed $\delta>0$ it is NP-hard to approximate $E_P(G)$ to within an additive error of $n^{2-\delta}$ .

Short context: How many edges we need to remove from a given graph G to make it, for example, triangle-free, or 3-colourable? The Theorem states that we can quickly solve any such problem approximately with error $\epsilon n^2$ but not with error $n^{2-\delta}$ for any $\delta>0$ . Before 2005, $\epsilon n^2$ approximation algorithm was not known even for triangle-free property, and the NP-hardness result was not known even for computing $E_P(G)$ exactly.

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

Go to the list of all theorems

Cayley graphs of symmetric groups can form explicit family of bounded-degree expanders

You need to know: Graph, graphs of bounded degree, group, symmetric group $\text{Sym}(n)$ (group of permutations of n symbols), notation $|A|$ for the number of elements in a finite set $A$ .

Background: $For a graph$ $\Gamma$ $h(\Gamma)=\min\limits_{1\leq |S|\leq |\Gamma|/2} \frac{|\partial S|}{|S|}$ $,$ $\Gamma$ An infinite family of graphs $\Gamma_1, \Gamma_2, \dots, \Gamma_n, \dots$ is a family of $\epsilon$ -expanders if $h(\Gamma_n)\geq \epsilon$ for all n.

A generating set of a group G is a subset $S \subset G$ such that every $g\in G$ can be written as a finite product of elements of S and their inverses. The (undirected) Cayley graph $\Gamma =\Gamma (G,S)$

The Theorem: On 28th May 2005, Martin Kassabov submitted to arxiv a paper in which he proved the existence of universal constants L and $\epsilon>0$ such that the following holds. For every n there exists a generating set $S_n$ of size at most L of the symmetric group $\text{Sym}(n)$ such that the Cayley graphs $\Gamma(\text{Sym}(n), S_n)$ form a family of $\epsilon$ -expanders.

Short context: Constructing explicit families of expanders is important, for example, for algorithmic applications. Although there are some combinatorial constructions, more traditional method is based on Cayley graphs of groups. Given an infinite family of finite groups, the problem is to construct generating sets to make their Cayley graphs expanders. The Theorem solves this problem for symmetric groups.

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

Go to the list of all theorems

Multidimensional Szemeredi’s theorem holds with an explicit bound

You need to know: Set ${\mathbb Z}^r$ of vectors with r integer components, notation $a+dX$ for set $\{y \in {\mathbb Z}^r\, : \, y=a+dx, \, x\in X\}$ , where $a \in {\mathbb Z}^r$ , $X \subset {\mathbb Z}^r$ , and $d>0$ is an integer.

Background: We say that number $N=N(x_1, \dots, x_m)$ is explicitly computable if there is an algorithm which takes $x_1, \dots x_m$ as an input and returns N as an output.

The Theorem: On 25th April 2005, Timothy Gowers submitted to the Annals of Mathematics a paper in which he proved that, for every $\delta > 0$ , every positive integer r, and every finite subset $X \subset {\mathbb Z}^r$ , there is an explicitly computable integer $N=N(\delta, r, X)>0$ , such that every subset $A$ of the grid $\{1, 2, . . . , N\}^r$ of size at least $\delta N^r$ has a subset of the form $a+dX$ for some $a \in {\mathbb Z}^r$ and integer $d>0$ .

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. In a paper submitted in 2000, Gowers proved that this statement holds with $N=\exp(\exp(\delta^c))$ , where $c=2^{-2^{k+9}}$ . The statement in the Theorem is a multidimensional version of Szemeredi’s theorem. The existence of $N=N(\delta, r, X)$ required in the Theorem was first proved by Furstenberg and Katznelson in 1978, but without any explicit algorithm how to actually compute this N. The Theorem provides such an algorithm.

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

Go to the list of all theorems

There are asymptotically C n^(-7/2) g^n n! labelled planar graphs on n vertices

You need to know: Graph, planar graph, labelled graph, factorial $n!=1\cdot 2 \cdot \dots \cdot n$ .

Background: For positive integer n, let $g(n)$ be the number of labelled planar graphs on n vertices. We write $g(n) \sim f(n)$ if $\lim\limits_{n\to\infty}\frac{g(n)}{f(n)}=1$ .

The Theorem: On 18th January 2005, Omer Gimenez and Marc Noy submitted to arxiv a paper in which they proved that $g(n) \sim C n^{-7/2}\gamma^n n!$ , where $\gamma = 27.22688\dots$ and $C = 0.0000042609\dots$ are explicit constants.

Short context: How many planar graphs are there? It is not difficult to show the existence of limit $\gamma = \lim\limits_{n\to\infty} \left(\frac{g(n)}{n!}\right)^{1/n}$ , but much more difficult to actually compute this limit. Many researchers provided better and better lower and upper bounds for $\gamma$ , with the best (before 2005) bounds $\gamma > 26.18$ by Bender, Gao and Wormald and $\gamma < 30.06$ by Bonichon et.al. The Theorem provides an exact analytical expression for $\gamma$ , which allows numerical computation up to arbitrary precision. Moreover, it provides the exact asymptotic formula for $g(n)$ .

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

Go to the list of all theorems

The Grothendieck constant of the complete n-vertex graph is at least c log n

You need to know: Euclidean space ${\mathbb R}^n$ , inner product $(x,y)=\sum\limits_{i=1}^n x_i y_i$ in ${\mathbb R}^n$ , unit vector in ${\mathbb R}^n$ , matrix, big O notation.

Background: For a positive integer n, let $K_n$ be the minimal constant such that for every $n \times n$ matrix with entries $a_{ij}$ and every unit vectors $x_1,\dots, x_n$ in ${\mathbb R}^n$ there are signs $e_1,\dots,e_n \in \{-1, +1\}$ for which $\sum\limits_{i \neq j} a_{ij}(x_i, x_j) \leq K_n \sum\limits_{i \neq j} a_{ij}e_ie_j$ . Constant $K_n$ is called the Grothendieck constant of the complete n-vertex graph, by analogy with the Grothendieck constant $K_G$ , see here.

The Theorem: On 8th November 2004, Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor submitted to Inventiones mathematicae a paper in which they proved, among other results, the existence of a constant $c>0$ such that $K_n \geq c \log n$ for all n.

Short context: In 1999, Nemirovski, Roos, and Terlaky proved that $K_n \leq C\log n$ for some constant C. Later, Megretski asked if this can be improved to $K_n \leq C$ . In 2004, Charikar and Wirth derived from inequality $K_n \leq C\log n$ various algorithms for combinatorial problems, and noticed that better upper bound on $K_n$ could lead to algorithms with better accuracy. The Theorem, however, proves that inequality $K_n \leq C\log n$ is optimal up to the constant factor.

Links: The original paper is available here.

Go to the list of all theorems

The Füredi-Hajnal Conjecture and the Stanley–Wilf Conjecture are true

You need to know: Matrix, submatrix, $O(n)$ notation, permutation of $\{1,2,\dots,n\}$ .

Background: Let A and P be $0$ – $1$ matrices (that is, matrices with all entries $0$ or $1$ ). We say that A contains the $k \times l$ matrix P with entries $p_{ij}$ if there exists a $k \times l$ submatrix D of A with entries $d_{ij}$ such that $d_{ij} = 1$ whenever $p_{ij} = 1$ . Otherwise we say that A avoids P. Let $f(n, P)$ be the maximum number of 1-entries in an $n \times n$ $0$ – $1$ matrix avoiding P. A $0$ – $1$ matrix P is called a permutation matrix if it has exactly one entry of $1$ in each row and each column and $0$ -s elsewhere.

The Theorem: On 18th December 2003, Adam Marcus and Gábor Tardos submitted to the Journal of Combinatorial Theory, Series A a paper in which they proved that for all permutation matrices P we have $f(n, P) = O(n)$ .

Short context: A permutation of $\{1,2,\dots,n\}$ is called an n-permutation. We say that an n-permutation $\sigma$ contains a k-permutation $\pi$ if there exist integers $1\leq x_1 < \dots < x_k \leq n$ such that for all $1 \leq i,j \leq k$ we have $\sigma(x_i) < \sigma(x_j)$ if and only if $\pi(i) < \pi(j)$ . Otherwise, we say that $\sigma$ avoids $\pi$ . For a fixed permutation $\pi$ , let $S_n(\pi)$ be the number of n-permutations avoiding $\pi$ . In the late 1980-s, Stanley and Wilf conjectured that for all $\pi$ there exists a constant $c_\pi$ such that $S_n(\pi) \leq c_\pi^n$ for all n. In 2000, Klazar proved that this conjecture follows from the 1992 conjecture of Füredi and Hajnal that $f(n, P) = O(n)$ for permutation matrices P. The Theorem confirms the Füredi-Hajnal Conjecture and hence the Stanley–Wilf Conjecture.

Links: The original paper is available here.

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

Vertex cover is unique-games-hard to approximate within any factor c < 2

You need to know: Graph, vertices, edges, class P, class NP, NP-hard problems, notation ${\mathbb Z}_m$ for set $\{0,1,2,\dots,m-1\}$ with addition and multiplication defined modulo m.

Background: A vertex cover of graph G is the set S of vertices of G such that for each edge $(u,v)$ of G either $u \in S$ or $v\in S$ (or both). Let $\tau(G)$ be the size of the smallest vertex cover of G. The minimum vertex cover problem is: given graph G, compute $\tau(G)$ . Its approximation with factor $c>1$ is: given graph G, compute number k such that $\tau(G) \leq k \leq c\tau(G)$ .

For a fixed $\epsilon \in (0,1/2)$ and integer m, consider the following problem. The input is a system of k linear equations in n variables $x_1, x_2, \dots, x_n$ over ${\mathbb Z}_m$ , each equation having the form $a \cdot x_i + b \cdot x_j = c$ , $a,b,c \in {\mathbb Z}_m$ , such that either (i) there is an assignment satisfying $(1-\epsilon) k$ of the equations, or (ii) no assignment satisfies more than $\epsilon k$ of the equations. The problem $\text{UG}(\epsilon,m)$ is to decide which of the cases (i) or (ii) is true. The Unique Games Conjecture states that for every $\epsilon \in (0,1/2)$ there exists m such that $\text{UG}(\epsilon,m)$ is NP-hard.

The Theorem: On 28th May 2003, Subhash Khot and Oded Regev submitted to the Journal of Computer and System Sciences a paper in which they proved that, assuming the Unique Games Conjecture, the minimum vertex cover problem is NP-hard to approximate to within any constant factor smaller than 2.

Short context: Because the minimum vertex cover problem is well-known to be NP-hard to solve exactly, it is natural to look for polynomial-time approximate algorithms. A simple algorithm, discovered independently by Gavril and Yannakakis, gives approximation with factor $c=2$ . The Theorem states that this approximation ratio is the best possible, subject to the Unique Games Conjecture. Unconditionally, it is known that the problem is NP-hard to approximate to within any factor $c<10\sqrt{5}-21 = 1.3606...$ . See here for further progress in later work.

Links: The original paper is available here.

Go to the list of all theorems