There exist nontrivial q-Steiner systems with t >= 2.

You need to know: field, vector space over a field, subspace of a vector space, dimension of a vector space, finite field ${\mathbb F}_q$ .

Background: Let ${\mathbb F}_q^n$ be a vector space of dimension n over the finite field ${\mathbb F}_q$ . A q-Steiner system, denoted $S_q(t,k,n)$ , is a set S of k-dimensional subspaces of ${\mathbb F}_q^n$ such that each t-dimensional subspace of ${\mathbb F}_q^n$ is contained in exactly one element of S. A q-Steiner system is called trivial if $t=k$ or $k=n$ and non-trivial otherwise.

The Theorem: On 4th April 2013, Michael Braun, Tuvi Etzion, Patric Ostergard, Alexander Vardy, and Alfred Wassermann submitted to arxiv a paper in which they proved the existence of non-trivial q-Steiner systems with $t>2$ . In fact, they proved the existence of over 500 different $S_2(2,3,13)$ q-Steiner systems.

Short context: Let V be a set with n elements, and let $k\geq 2$ . A Steiner system $S(t,k,n)$ is a collection of k-subsets of V, called blocks, such that each t-subset of V is contained in exactly one block. Steiner systems are among the most beautiful and well-studied structures in combinatorics, see here. In 1974, Cameron suggested to study $S_q(t,k,n)$ , a natural analogue of Steiner system over finite fields. However, despite efforts of many researchers, such systems has been known only for $t=1$ , and in the trivial cases $t=k$ and $k=n$ . The Theorem provides us with first examples of non-trivial q-Steiner systems with $t\geq 2$ .

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

Go to the list of all theorems

The list chromatic number of a graph with average degree d is at least (1+o(1))log_2 d

You need to know: Graph, simple graph (one with no loops and multiple edges), degree of a vertex in the graph, average degree of a graph, small o notation. You also need to know chromatic number of graph and complete bipartite graph $K_{d,d}$ for the context section.

Background: A graph G is called k-choosable if, whenever for each vertex v of G we assign a list $L_v$ of k colours to v, then it is possible to choose a colour for v from the list $L_v$ , so that no two adjacent vertices receive the same colour. The list chromatic number $\chi_l(G)$ is the smallest k such that G is k-choosable.

The Theorem: On 30th April 2012, David Saxton and Andrew Thomason submitted to arxiv a paper in which they proved, among other results, that if G is a simple graph with average degree d, then $\chi_l(G) \geq (1+o(1))\log_2 d$ as $d\to \infty$ .

Short context: List chromatic number $\chi_l(G)$ is a natural version of the ordinary chromatic number $\chi(G)$ of G (which corresponds to the case when all $L_v$ are the same). It is known that $\chi_l(K_{d,d})=(1+o(1))\log_2 d$ , in sharp contrast with $\chi(K_{d,d})=2$ . In fact, Alon proved that $\chi_l(G) \geq (1/2+o(1))\log_2 d$ for graphs G of minimum degree d. The Theorem improves this inequality by a factor of 2 and is the best possible, as example $G=K_{d,d}$ shows. In fact, the Theorem is just one out of many corollaries of the general theorem proved by the authors, see the original paper for details.

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

Go to the list of all theorems

Sparse analog of Szemerédi’s theorem is true

You need to know: A (nontrivial) k-term arithmetic progression, notation $[n]$ for $\{1,2,\dots,n\}$ .

Background: For integer $m>0$ and real number $x\geq m$ , denote ${{x}\choose{m}}=\frac{1}{m!}\prod\limits_{i=0}^{m-1}(x-i)$ . By convention, we define ${{x}\choose{m}}=0$ if $x<m$ . Also, by m-subset of $[n]$ we mean a subset which has m elements.

The Theorem: On 29th April 2012, József Balogh, Robert Morris, and Wojciech Samotij submitted to arxiv a paper in which they proved, among other results, that for every real $\beta>0$ and every integer $k\geq 3$ , there exist constants C and $n_0>0$ such that for every integers $n \geq n_0$ and $m\geq Cn^{1-1/(k-1)}$ , there are at most ${{\beta n}\choose{m}}$ m-subsets of $[n]$ that contain no k-term arithmetic progression.

Short context: Famous Szemerédi’s theorem, proved in 1975, states that, for every $\beta>0$ , every subset of $[n]$ of size $m\geq \beta n$ must contain a k-term arithmetic progression, provided that n is sufficiently large. The authors view the Theorem as a sparse analog of this statement. It easily implies the original Szemerédi’s theorem, as well as its sparse random analog described here. In turn, the Theorem itself is just one out of many corollaries of the general powerful theorem in graph theory proved by the authors, see the original paper for details.

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

Go to the list of all theorems

The clique density conjecture of Lovász and Simonovits is true

You need to know: Graph, clique in a graph, size of a clique, factorial $n!=1\cdot 2 \cdot \dots \cdot n$ with convention that $0!=1$ , notation ${n}\choose{k}$ for $\frac{n!}{k!(n-k)!}$ , with convention that ${{n}\choose{k}}=0$ if $n<k$ .

Background: For $\gamma\in[0,1/2)$ , let $s_{\gamma}$ be the unique positive integer such that $\gamma \in \left[\frac{s_{\gamma}-1}{2s_{\gamma}}, \frac{s_{\gamma}}{2(s_{\gamma}+1)}\right)$ , and let $\alpha_{\gamma}\in(0,1/\gamma]$ be the real number such that $\gamma=\frac{s_{\gamma}}{2(s_{\gamma}+1)}(1-\alpha_{\gamma}^2)$ .

The Theorem: On 19th January 2012, Christian Reiher submitted to arxiv and the Annals of Mathematics a paper in which he proved that, for every integer $r\geq 3$ and real $\gamma\in[0,1/2)$ , every graph on n vertices with at least $\gamma n^2$ edges contains at least $\frac{1}{(s_\gamma+1)^r}{{s_\gamma+1}\choose{r}}(1+\alpha_\gamma)^{r-1}(1-(r-1)\alpha_\gamma)\cdot n^r$ cliques of size r.

Short context: Famous Turán’s theorem, proved in 1941, states that for any integer $r\geq 3$ , every graph on n vertices with more than $\frac{r-2}{2(r-1)}n^2$ edges contains a clique of size r. A natural question arises to estimate the minimum number $g_r(n,e)$ of r-cliques a graph with n vertices and e edges must contain. The Theorem proves a lower bound for $g_r(n,e)$ , predicted by Lovász and Simonovits in 1983, which was known as the clique density conjecture. Together with known upper bound, the Theorem allows to exactly determine, for any $\lambda\in[0,1]$ , the limit $g_r(\lambda)=\lim\limits_{n\to\infty}\frac{g_r(n,e(n))}{{{n}\choose{r}}}$ , whenever $\lim\limits_{n\to\infty} \frac{e(n)}{{{n}\choose{2}}}=\lambda$ . See here for further progress in computing $g_3(n,e)$ exactly.

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

Go to the list of all theorems

The chromatic threshold of a graph H with chromatic number r>=3 can be (r-3)/(r-2), (2r-5)/(2r-3), or (r-2)/(r-1)

You need to know: Graph, isomorphic graphs, subgraph, degree of a vertex of graph G, chromatic number $\chi(G)$ of graph G.

Background: We say that graph G has minimum degree at least M if the degree of each vertex of G is at least M. A graph G is called H-free, if it does not have a subgraph isomorphic to H. The chromatic threshold $\delta_\chi(H)$ of a graph H is the infimum of $d>0$ such that there exists $C=C(H,d)$ for which every H-free graph G with minimum degree at least $d|G|$ satisfies $\chi(G) \leq C$ .

The Theorem: On 8th August 2011, Peter Allen, Julia Böttcher, Simon Griffiths, Yoshiharu Kohayakawa, and Robert Morris submitted to arxiv a paper in which they proved that the chromatic threshold of every graph H with $\chi(H)=r\geq 3$ must be either $\frac{r-3}{r-2}$ , or $\frac{2r-5}{2r-3}$ , or $\frac{r-2}{r-1}$ .

Short context: In 1940th, Zykov and Tutte constructed triangle-free graphs
with arbitrarily large chromatic number. In 1959, Erdős did the same for H-free graphs for any graph H containing a cycle. In 1973, Erdős and Simonovits suggested to investigate this question for graphs with large minimum degree, defined the chromatic threshold $\delta_\chi(H)$ , and asked to determine $\delta_\chi(H)$ for every graph H. The Theorem lists 3 possible values for $\delta_\chi(H)$ for every graph H with $\chi(H)\geq 3$ . The authors also determined exactly for which graphs H $\delta_\chi(H)$ is equal to each value. Together with known fact that $\delta_\chi(H)=0$ if $\chi(H)\leq 2$ , this answers the question of Erdős and Simonovits for all graphs H.

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

Go to the list of all theorems

There exist e>0 and C such that if A is a cap set in F_3^N, then |A|/3^N < C/N^(1+e)

You need to know: Addition modulo 3, vectors, notation $|A|$ for the number of elements in finite set A.

Background: Let ${\mathbb F}_3$ be the set $\{0,1,2\}$ with addition defined modulo 3. Let ${\mathbb F}_3^N$ be the set of N-component vectors $x=(x_1, \dots, x_N)$ with each $x_i \in {\mathbb F}_3$ , and with addition defined component-wise. We say that three different points $x,y,z\in {\mathbb F}_3^N$ form a line if $x+y=z+z$ . A set $A \subseteq {\mathbb F}_3^N$ is called a cap set if it contains no lines.

The Theorem: On 31st January 2011, Michael Bateman and Nets Katz submitted to arxiv a paper in which they proved the existence of $\epsilon>0$ and $C<\infty$ such that if $A \subseteq {\mathbb F}_3^N$ is a cap set, then $\frac{|A|}{3^N} \leq \frac{C}{N^{1+\epsilon}}$ .

Short context: What can the maximal size of a cap set in ${\mathbb F}_3^N$ ? This problem is interesting in its own, but also studied because of hope that methods to solve it may be useful for the similar problem of finding dense sets of integers without 3-term arithmetic progressions, see here. A cap set conjecture predicts the existence of constant $c<3$ such that $|A|<c^N$ for every cap set $A \subseteq {\mathbb F}_3^N$ . However, before 2011, the best upper bound was $\frac{|A|}{3^N} \leq \frac{C}{N}$ , proved by Meshulam in 1995. The Theorem improves this bound.

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

Go to the list of all theorems

Szemerédi’s theorem holds almost surely inside sparse random sets

You need to know: A (nontrivial) k-term arithmetic progression, notation $|I|$ for the number of elements in finite set I, notation P for probability, independence.

Background: Let $[n]=\{1,2,\dots,n\}$ , and let $[n]_p$ be a random subset of $[n]$ in which each element of $[n]$ is chosen independently with probability $p\in[0,1]$ . A finite set I of integers is called $(\delta; k)$ -Szemerédi if every subset of I of cardinality at least $\delta|I|$ contains a nontrivial k-term arithmetic progression.

The Theorem: On 18th November 2010, Daniel Conlon and Timothy Gowers submitted to arxiv and the Annals of Mathematics a paper in which they proved, among other results, that for any $\delta>0$ and any integer $k\geq 3$ , there exists a constant $C=C(k,\delta)$ such that $\lim\limits_{n\to\infty} P([n]_p \text{ is } (\delta; k) \text{-Szemeredi})=1$ if $p \geq \min\{1, Cn^{-1/(k-1)}\}$ .

Short context: Famous Szemerédi’s theorem, proved in 1975, states, in our terminology, that set $[n]$ itself is $(\delta; k)$ -Szemerédi for all $n\geq N(\delta,k)$ . Later, Green and Tao, on the way of proving this theorem, proved the existence of function $p=p(n)$ with $\lim\limits_{n\to\infty} p(n)=0$ such that $\lim\limits_{n\to\infty} P([n]_p \text{ is } (\delta; k) \text{-Szemeredi})=1$ . The Theorem proves that the same conclusion holds for every function $p=p(n)$ such that $p \geq Cn^{-1/(k-1)}$ . This result is optimal up to constant factor because it is known that, for some constant $c=c(k,\delta)>0$ , $\lim\limits_{n\to\infty} P([n]_p \text{ is } (\delta; k) \text{-Szemeredi})=0$ whenever $p \leq cn^{-1/(k-1)}$ . Before 2010, the Theorem was known to hold only for $k=3$ . See here for further generalisation 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 absolute values of the coefficients of the chromatic polynomial form a log-concave sequence

You need to know: Graph, proper colouring of vertices of a graph, polynomial.

Background: A sequence $x_0, x_1, \dots, x_n$ of real numbers is called log-concave if $x_{i-1}x_{i+1} \leq x_i^2$ for all $0<i<n$ . For a finite graph G and integer $q>0$ , let $\chi_G(q)$ be the number of proper colouring of vertices of G with q colours. It is known that $\chi_G(q)$ is in fact a polynomial $\chi_G(q)=\sum\limits_{k=0}^n (-1)^{n-k}a_k q^k$ , where $a_0, a_1 \dots, a_n$ are non-negative integers.

The Theorem: On 27th August 2010, June Huh submitted to arxiv a paper in which he proved that if $\chi_G(q)=\sum\limits_{k=0}^n (-1)^{n-k}a_k q^k$ is the chromatic polynomial of a graph G, then the sequence $a_0, a_1 \dots, a_n$ is log-concave.

Short context: The chromatic polynomial was introduced by Birkhoff in 1912, and is one of the most beautiful objects of study in graph theory. In 1968, Read conjectured that the sequence of the absolute values of the coefficients of the chromatic polynomial is unimodal (that is, $a_0 \leq a_1 \leq \dots \leq a_{i-1} \leq a_i \geq a_{i+1} \geq \dots \geq a_n$ for some $0 \leq i \leq n$ ). In 1971, Rota conjectured that this sequence is in fact log-concave and observed that this would imply the Read’s conjecture. The Theorem confirms this prediction. In fact, Rota conjectured an even more general statement, which was also proved 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

Algorithmic version of general Lovász local lemma is true

You need to know: Probability, probability space, event, random variable, mutually independent random variables.

Background: Let ${\cal P}$ be a finite collection of mutually independent random variables in a fixed probability space $\Omega$ . Let $S$ be a finite family of events in $\Omega$ determined by ${\cal P}$ . For $A\in S$ , let $v(A)$ be the (unique) minimal subset of ${\cal P}$ that determines $A$ . For $A\in S$ , let $\Gamma_S(A)$ be the set of $B\in S$ such that $A\neq B$ but $v(A)\cap v(B) \neq \emptyset$ . We say that an evaluation of the variables in ${\cal P}$ violates $A\in S$ if it makes A happen.

The Theorem: On 3rd March 2009, Robin Moser and Gábor Tardos submitted to arxiv a paper in which they proved that if there exists an assignment of reals $x:S \to (0,1)$ such that $\forall A\in S: \text{Prob}[A]\leq x(A) \prod\limits_{B\in \Gamma_S(A)} (1-x(B))$ , then there exists an assignment of values to the variables in ${\cal P}$ not violating any of the events in S. Moreover, this assignment can be found by a randomised algorithm with the expected number of resampling steps at most $\sum\limits_{A\in S}\frac{x(A)}{1-x(A)}$ .

Short context: The Theorem without “moreover” part is (a slightly modified version of) famous Lovász local lemma, discovered by Erdős and Lovász in 1975, which allows one to show the existence of certain objects occurring with exponentially small probability. The “moreover” part of the Theorem can be used to actually construct such objects. Previously, algorithmic versions where developed for some applications of the Lovász local lemma, but not for the lemma in general.

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

Go to the list of all theorems

The Hirsch Conjecture is false

You need to know: d-dimensional polytope, its vertices, edges, and facets.

Background: A (combinatorial) diameter of a polytope is the maximum number of steps needed to go from one vertex to another, where a step consists in traversing an edge.

The Theorem: On 14th June 2010, Francisco Santos submitted to arxiv a paper in which he proved the existence of a 43-dimensional polytope with 86 facets and diameter at least 44.

Short context: In 1957, Hirsch conjectured that d-dimensional polytope with n facets cannot have diameter greater than $n-d$ . The conjecture has applications to the complexity of the simplex method for linear programming. It was well-believed and proved in some special cases. Because $44>86-43$ , the Theorem provides a counterexample to this conjecture.

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

Go to the list of all theorems