2) is subcomplete

You need to know: Notation ${\mathbb N}$ for the set of natural numbers, notation $|B|$ for the number of elements in set B, arithmetic progression.

Background: Let ${\cal A}\subset {\mathbb N}$ be an infinite set of natural numbers (without repetitions). We say that ${\cal A}$ has density at least $f(n)$ if $|{\cal A}\cap\{1,2,\dots,n\}|\geq f(n)$ for all sufficiently large n. Let $S_A=\{\sum\limits_{x\in B} x\,|\,B\subset {\cal A}, |B|<\infty\}$ be the set of all possible sums of finite number of elements of ${\cal A}$ . We say that ${\cal A}$ is subcomplete if $S_A$ contains an infinite arithmetic progression.

The Theorem: On 19th March 2003, Endre Szemerédi and Van Vu submitted to the Annals of Mathematics a paper in which they proved the existence of constant $c>0$ such that every set ${\cal A}\subset {\mathbb N}$ with density at least $c\sqrt{n}$ is subcomplete.

Short context: We say that set ${\cal A}$ is complete if $S_A$ contains all sufficiently large integers. This notion was introduced by Erdős in the sixties. It is well studied, the central problem being to find sufficient conditions for completeness. In 1962, Erdős conjectured the existence of $c>0$ such that if (i) ${\cal A}$ has density at least $c\sqrt{n}$ and (ii) $S_A$ contains an element of every infinite arithmetic progression, then ${\cal A}$ is complete. In 1966, Folkman conjectured that every ${\cal A}$ satisfying (i) is subcomplete and deduced the Erdős conjecture from this. The Theorem confirms the Folkman conjecture and hence the Erdős conjecture.

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

Go to the list of all theorems

Perfect graphs can be recognised in polynomial time

You need to know: Polynomial-time algorithms, basic graph theory: graph, size of a graph (number of its vertices), induced subgraph, complete sugraph, cycle, length of the cycle, complement of a graph, chromatic number of a graph, big O notation.

Background: A graph G is perfect if for every induced subgraph H, the chromatic
number of H equals to the size of the largest complete subgraph of H. The problem of perfect graph recognition is: given a graph as an input, determine whether it is perfect or not.

The Theorem: On 26th February 2003, Maria Chudnovsky, Gérard Cornuéjols, Xinming Liu, Paul Seymour, and Kristina Vušković submitted to Combinatorica a paper in which they proved that the problem of perfect graph recognition for n-vertex graphs can be solved in time $O(n^9)$ .

Short context: An odd hole is a cycle of odd length $n\geq 5$ and odd antihole is the complement of odd hole. A graph G is Berge if it does not contain an odd hole or an odd antihole as an induced subgraph. The Theorem in fact provides an algorithm for recognising Begre graphs. However, by an earlier result of Chudnovsky, Robertson, Seymour, and Thomas, a graph G is perfect if and only if it is Begre. This gives the first polynomial-time algorithm for recognising perfect graphs.

Links: The original paper is available here.

Go to the list of all theorems

The strong perfect graph conjecture is true: all Berge graphs are perfect

You need to know: Basic graph theory: graph, size of a graph (number of its vertices), induced subgraph, complete sugraph, cycle, length of the cycle, complement of a graph, chromatic number of a graph.

Background: A graph G is perfect if for every induced subgraph H, the chromatic
number of H equals to the size of the largest complete subgraph of H. An odd hole is a cycle of odd length $n\geq 5$ and odd antihole is the complement of odd hole.

The Theorem: On 4th December 2002, Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas submitted to arxiv a paper in which they proved that a graph G is perfect if and only if it does not contain an odd hole or an odd antihole as an induced subgraph.

Short context: In 1961, Berge observed that every perfect graph G does not contain an odd hole or an odd antihole, and conjectured that the converse is true. This conjecture became known as the strong perfect graph conjecture and attracted a lot of attention. Graphs with no odd hole or antihole got the name Berge graphs and the conjecture then states that all Berge graphs are perfect (which implies that the perfect graphs and the Berge graphs define the same class of graphs). The Theorem proves this conjecture and have got the name strong perfect graph theorem. The proof of the strong perfect graph theorem won for its authors several prizes including the 2009 Fulkerson Prize.

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

Go to the list of all theorems

Fast algorithm for the number of solutions in the coin problem with fixed n

You need to know: Coprime integers, algorithm working in polynomial time, NP-hard problem.

Background: Given positive coprime integers $a_1, a_2, \dots, a_n$ , denote $S(a_1, a_2, \dots, a_n)$ the (always finite) set of positive integers which cannot be represented as $\sum\limits_{i=1}^n m_i a_i$ for some non-negative integers $m_1, m_2, \dots m_n$ .

The Theorem: On 8th November 2002, Alexander Barvinok and Kevin Woods submitted to arxiv a paper in which they, among other results, proved the existence of an algorithm, which, given $a_1, a_2, \dots, a_n$ , computes the number of integers in $S(a_1, a_2, \dots, a_n)$ in polynomial time for any fixed n.

Short context: The Frobenius coin problem, studied at least from 1882, asks to compute the largest integer in $S(a_1, a_2, \dots, a_n)$ . The problem is known to be NP-hard if n is part of the input. However, Kannan presented in 1992 a polynomial algorithm to solve it for every fixed n. The Theorem states that, for fixed n, the number of elements in $S(a_1, a_2, \dots, a_n)$ can also be computed efficiently.

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

Go to the list of all theorems

Ergodic averages, taken along cubes whose sizes tend to infinity, converge in L^2

You need to know: Set ${\mathbb Z}^k$ of vectors $x=(x_1,\dots,x_k)$ with integer coordinates, addition in ${\mathbb Z}^k$ , set ${\mathbb N}$ of natural numbers, $\limsup$ notation.

Background: The upper density $d(A)$ of set $A \subset {\mathbb N}$ is $d(A)=\limsup\limits_{N\to \infty} \frac{1}{N}|A \cap \{1,2,\dots,N\}|$ . For any $A \subset {\mathbb Z}^k$ and $x\in {\mathbb Z}^k$ the translate $A+x$ is $\{y: \, y=a+x, \, a\in A \}$ . Let $t(A)$ be the minimal number of translates of A needed to fully cover ${\mathbb Z}^k$ . Set A is called syndetic if $t(A)<\infty$ . Also, denote $V_k \subset {\mathbb Z}^k$ the set of vectors $x=(x_1,\dots,x_k)$ with all coordinates $0$ or $1$ .

The Theorem: On 16th June 2002, Bernard Host and Bryna Kra submitted to the Annals of Mathematics a paper in which they proved that for any $A \subset {\mathbb N}$ with $d(A) > \delta > 0$ and integer $k \geq 1$ , the set of $n=(n_1, n_2, \dots, n_k) \in {\mathbb Z}^k$ such that $d\left(\bigcap\limits_{\epsilon\in V_k}\left(A + \sum\limits_{i=1}^k\epsilon_i n_i\right)\right) \geq \delta^{2^k}$ is syndetic.

Short context: The Theorem, as stated above, is a combinatorial reformulation of a deep theorem is the field of ergodic theory, which establishes $L^2$ -convergence of so-called “ergodic averages taken along cubes whose sizes tend to infinity”. The details of this original formulation are too difficult to be presented here.

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

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

In any infinite sequence of graphs, some graph is a minor of some other one

You need to know: (Undirected, finite) graph, isomorphic graphs, operations of edge contraction, edge deletion, and vertex deletion.

Background: A graph H is a minor of graph G if H can be obtained from G by a sequence of contractions of edges of G, and deletions of edges and vertices of G.

The Theorem: On 13th February 2001, Neil Robertson and Paul Seymour submitted to the Journal of Combinatorial Theory, Series B, a paper in which they proved that in any infinite sequence $G_1, G_2, \dots$ of graphs, one can select two graphs, $G_i$ and $G_j$ , such that one of them is isomorphic to a minor of another one.

Short context: A family ${\cal F}$ of graphs if called minor-closed if $G \in {\cal F}$ implies that $H \in {\cal F}$ for all minors H of G. For example, if $H_1, H_2, \dots, H_n$ is any finite set of graphs, then the family ${\cal F}$ of graphs G that do not have any of $H_i$ as a minor is obviously minor-closed. The Theorem implies that in fact any minor-closed family can be represented in this way. This statement was known as Wagner’s conjecture (although Wagner said he never conjectured it!) and is now known as the Robertson-Seymour theorem, or the graph minor theorem. The Theorem was proved in a series of 20 papers of total length over 500 pages (the date 13th February 2001 is the submission date of the last paper).

Links: The original paper is available here.

Go to the list of all theorems

Complete graph of odd order can be decomposed into equal-length cycles

You need to know: Basic graph theory: graph, vertex, edge, order of graph (number of vertices), complete graph, cycle, length of the cycle, degree of a vertex, subgraph, isomorphic graphs, perfect maching.

Background: We denote $K_n$ the complete graph on n vertices. For even n, we denote $K'_n$ the complete graph on n vertices with a perfect maching removed. Also, let $C_m$ denote a cycle of length m. We say that graph G is decomposed into its subgraphs $H_1$ and $H_2$ , and write $G = H_1 \oplus H_2$ , if G is the edge disjoint union of $H_1$ and $H_2$ . We cay that G is H-decomposable, if $G = H_1 \oplus H_2 \oplus \dots \oplus H_k$ , where each $H_i$ is isomorphic to H.

The Theorem: On 28th November 2000, Mateja Šajna submitted to the Journal of Combinatorial Designs a paper in which she proved that (i) for every odd $n\geq 3$ and every m such that $3\leq m \leq n$ and m divides the number of edges in $K_n$ , graph $K_n$ is $C_m$ -decomposable; (ii) for every even $n\geq 4$ and every m such that $3\leq m \leq n$ and m divides the number of edges in $K'_n$ , graph $K'_n$ is $C_m$ -decomposable.

Short context: When can we decompose the complete graph $K_n$ into cycles of some fixed length m? Obviously, this can be possible only if $3\leq m \leq n$ and m divides the number of edges in $K_n$ . Also, the degrees of all vertices of $K_n$ should be even. Hence, n should be odd. The Theorem proves that these obvious necessary conditions are in fact sufficient, culminating a long series of papers with partial results. It also establishes a similar result for even n, in which case perfect matching is removed from $K_n$ to make the vertices degrees even.

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

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