The family {x, xy, x+y} is Ramsey

You need to know: Set ${\mathbb N}$ of positive integers

Background: By finite colouring of ${\mathbb N}$ we mean partition ${\mathbb N}=C_1\cup\dots\cup C_r$ into a finite number r of disjoint subsets $C_i$ . We say that set $S \subset {\mathbb N}$ is monochromatic if $S \subset C_i$ for some i.

The Theorem: On 4th May 2016, Joel Moreira submitted to the Annals of Mathematics a paper in which he proved that for any finite colouring of ${\mathbb N}$ there exist (infinitely many) pairs $x,y \in {\mathbb N}$ such that the set $\{x, xy, x + y\}$ is monochromatic.

Short context: A set of k polynomials $P_1,\dots, P_k$ in s variables $x_1, \dots, x_s$ with integer coefficients is called a Ramsey family if for any finite colouring of ${\mathbb N}$ there exist $x_1, \dots, x_s \in {\mathbb N}$ such that the set $P_1(x_1, \dots, x_s),\dots, P_k(x_1, \dots, x_s)$ is monochromatic. A classical problem asks to develop necessary and sufficient conditions on the polynomials $P_1,\dots, P_k$ that guarantee that they form a Ramsey family. However, before 2016, it was not even known if a simple family $\{xy, x + y\}$ is Ramsey. The Theorem establishes this, even for a lager family $\{x, xy, x + y\}$ . In fact, the authors developed a general methodology and established that many other families are Ramsey as well. See here and here for related recent results.

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

Go to the list of all theorems

The boolean Pythagorean Triples problem has a positive answer

You need to know: Notation ${\mathbb N}$ for the set of positive integers.

Background: A Pythagorean triple is a set of three positive integers a, b, and c, such that $a^2+b^2=c^2$ .

The Theorem: On 3rd May 2016, Marijn Heule, Oliver Kullmann, and Victor Marek submitted to arxiv a paper in which they proved the following result. The set $\{1,\dots,7824\}$ can be partitioned into two parts, such that no part contains a Pythagorean triple, while this is impossible for $\{1,\dots,7825\}$ .

Short context: The boolean Pythagorean Triples problem has been a longstanding open problem in Ramsey Theory. It asks whether in every partition of the set ${\mathbb N}$ of positive integers into two parts, one can always find a Pythagorean triple in one of the parts. There was a progress in the variants of the problem (see here and here), but the original problem remained open. The Theorem provides a positive answer. In fact, it guarantees that one can find a Pythagorean triple in every partition of the set of first 7825 positive integers, and that 7825 is the smallest integer with this property. The computer-assisted proof is almost 200 terabytes in size.

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

Go to the list of all theorems

All Robbins conjectures on the number of ASMs with symmetries are true

You need to know: Notation $n!=1\cdot 2 \cdot \dots \cdot n$ , 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 diagonally and antidiagonally symmetric (DASASM) if $a_{ij} = a_{ji} = a_{n+1-j,n+1-i}$ for all $1\leq i,j \leq n$ .

The Theorem: On 18th December 2015, Roger Behrend, Ilse Fischer, and Matjaž Konvalinka submitted to arxiv a paper in which they proved that, for any positive integer n, the number of $(2n+1)\times(2n+1)$ DASASMs is given by $\prod\limits_{i=0}^{n} \frac{(3i)!}{(n+i)!}$ .

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 the total number of ASMs 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. For many years, these conjecture served as a roadmap, stimulating progress in the area. Starting from work of Kuperberg, see here, several groups of researchers resolved by 2006 all these conjectures except one: the formula for the number of $(2n+1)\times(2n+1)$ DASASMs. The Theorem resolves this remaining conjecture.

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

Go to the list of all theorems

Rota’s and Mason’s log-concavity conjectures are true for all matroids

You need to know: Notations: $\emptyset$ for the emply set, $|X|$ for the number of elements in finite set X (also called the cardinality of X), $2^X$ for the set of all subsets of X, $A \setminus B$ for the set $\{x: x\in A \,\text{and}\,x\not\in B\}$ .

Background: A (finite) matroid is a pair $(X,I)$ , where X is a finite set and $I \subset 2^X$ is a family of its subsets, such that (i) $\emptyset \in I$ ; (ii) if $A \in I$ and $A' \subseteq A$ then $A' \in I$ ; and (iii) if $A \in I$ , $B \in I$ , and $|A|>|B|$ , then there exists $x \in A \setminus B$ such that $B \cup \{x\} \in I$ . The rank of M is $r(M)=\max\limits_{B\in I}|B|$ . Similarly, the rank of any subset $A \subset X$ is $r(A)=\max\limits_{B\in I, \, B\subseteq A}|B|$ . Polynomial $\chi_M(\lambda)=\sum\limits_{A\subseteq X}(-1)^{|A|}\lambda^{r(M)-r(A)}$ is called the characteristic polynomial of matroid M. For $k=0,1,\dots,r(M)$ , let $w_k(M)$ be the absolute value of the coefficient of $\lambda^{r(M)-k}$ in $\chi_M(\lambda)$ . Also, let $f_k(M)$ be the number of sets $A \in I$ with $|A|=k$ . A sequence $a_0, \dots, a_n$ of non-negative real numbers in called log-concave if $a_{k-1}a_{k+1} \leq a_k^2$ for $0<k<n$ .

The Theorem: On 9th November 2015, Karim Adiprasito, June Huh, and Eric Katz submitted to arxiv a paper in which they proved that for any matroid M (i) the sequence $w_0(M), \dots, w_{r(M)}(M)$ is log-concave, and (ii) the sequence $f_0(M), \dots, f_{r(M)}(M)$ is log-concave.

Short context: Part (i) of the Theorem confirms a famous conjecture of Rota made in 1971. This conjecture generalises many important conjectures and theorems. For example, this theorem of Huh about log-concavity of the coefficients of chromatic polynomials of graphs is a very special case of part (i) of the Theorem when M is so-called graphic matroid. Part (ii) of the Theorem confirms a related conjecture of Mason made in 1972.

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

Go to the list of all theorems

An explicit construction of a 2^((log log n)^c)-Ramsey graph over n vertices

You need to know: Graph, clique, independent set, small o notation, polynomial time algorithm.

Background: A graph on n vertices is called a k-Ramsey graph if it contains no clique or independent set of size k. By an explicit construction of a k-Ramsey graph we mean a polynomial time algorithm that, given the labels of two vertices in the graph, determines whether there is an edge between them. For n-vertex graph, the input of such algorithm has $2\log n$ bits, hence the running time should be polynomial in $\log n$ .

The Theorem: On 14th June 2015, Gil Cohen submitted to arxiv a paper in which he proved the existence of an absolute constant $c$ such that there is an explicit construction of a $2^{(\log \log n)^c}$ -Ramsey graph over $n$ vertices.

Short context: In 1947 Erdős used the probabilistic method to show that most graphs on $n$ vertices are $(2+o(1))\log n$ -Ramsey. Interestingly, there is no known explicit example of such a graph for large n. Before 2015, the best explicit construction was achieved by Barak, Rao, Shaltiel, and Wigderson, who constructed k-Ramsey $n$ -vertex graphs for $k = 2^{2^{{(\log \log n)}^{1-\epsilon}}}$ , see here. The Theorem provides a significantly better construction. The same result was achieved independently by Chattopadhyay and Zuckerman, who posted their paper online on 23rd July 2015. In a later work (submitted in 2018), Li gave an even better explicit construction achieving $k=(\log n)^{o(\log \log \log n)}$ .

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

Go to the list of all theorems

The Ramsey number of any n-vertex d-degenerate graph is at most c_d n

You need to know: Graph, subgraph, degree of a vertex in a graph, notation $K_n$ for the complete graph on n vertices.

Background: For a graph H, the Ramsey number of H, denoted $r(H)$ , is the minimum integer m such that in every edge two-colouring of $K_m$ there exists a monochromatic copy of H. A graph H is called d-degenerate if all its subgraphs contain a vertex of degree at most d.

The Theorem: On 18th May 2015, Choongbum Lee submitted to arxiv a paper in which he proved that for every positive integer d there is a constant $c=c(d)$ such that every d-degenerate graph H on n vertices satisfies $r(H) \leq cn$ .

Short context: In 1930, Ramsey proved that $r(K_n)$ are finite for all positive integers n. This result originated a large body of research, which is now considered as one of the most important research directions in combinatorics, see here and here for some resent results. In 1973, Burr and Erdős initiated the study of Ramsey numbers of sparse graphs, suggested d-degeneracy as a measure of sparseness, and conjectured that, for any fixed d, the Ramsey numbers of n-vertex d-degenerate graphs is bounded by a linear function of n. This is in striking contrast with the case of complete graphs where $r(K_n)$ grows exponentially in n. The Theorem confirms this conjecture.

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

Go to the list of all theorems

The topological Tverberg conjecture is false

You need to know: Eucledean space ${\mathbb R}^d$ , continuous map $f: {\mathbb R}^m \to {\mathbb R}^d$ , image of a set under map f, polytope, face of a polytope, convex hull, prime numbers, power of a prime.

Background: An m-simplex, denoted $\Delta_m$ , is an m-dimensional polytope which is the convex hull of its $m+1$ vertices. The “topological Tverberg conjecture” states that for given integers $r\geq 2$ , $d \geq 1$ , $m \geq (r-1)(d+1)$ , and for any continuous map $f: \Delta_m \to {\mathbb R}^d$ , there are r pairwise disjoint faces of $\Delta_m$ whose images have a point in common.

The Theorem: On 1st February 2015, Florian Frick submitted to arxiv a paper in which he proved that the topological Tverberg conjecture is false for any r that is not a power of a prime and any dimension $d \geq 3r+1$ .

Short context: The topological Tverberg conjecture was formulated by Bárány, Shlosman and Szűcs in 1981, and was considered by many experts as a major open problem, a holy grail of topological combinatorics. The case when f is an affine map is equivalent to Tverberg’s 1966 theorem (hence the name of the conjecture). The conjecture was also known to hold when r is a prime or a power of a prime, and was commonly believed to be true in general. The Theorem refutes the conjecture.

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

Go to the list of all theorems

The existence conjecture for combinatorial designs is true

You need to know: Factorial $n!=1\cdot 2 \cdot \dots \cdot n$ with convention that $0!=1$ , notation ${n}\choose{k}$ for $\frac{n!}{k!(n-k)!}$ .

Background: We say that a family S of q-elements subsets of an n-element set X is a (combinatorial) design with parameters $(n, q, r, \lambda)$ if every r-element subset of X belongs to exactly $\lambda$ sets in S. We say that positive integers $(n, q, r, \lambda)$ satisfy the divisibility conditions if $r\leq q \leq n$ and ${{q-i}\choose{r-i}}$ divides $\lambda{{n-i}\choose{r-i}}$ for every $0\leq i \leq r-1$ .

The Theorem: On 15th January 2015, Peter Keevash submitted to arxiv a paper in which he proved that for any fixed positive integers q, r, and $\lambda$ , there exist $n_0=n_0(q, r, \lambda)$ such that if $n \geq n_0$ and $(n, q, r, \lambda)$ satisfy the divisibility conditions then a design with parameters $(n, q, r, \lambda)$ exists.

Short context: The statement of the Theorem was known as the existence conjecture for combinatorial designs and was the central open question in design theory. In 1975, Wilson proved this conjecture for $r=2$ , which already was recognised as a major achievement. The Theorem proves the conjecture in general. The result is new even for $\lambda=1$ , in which case combinatorial design is called Steiner system. Steiner systems are studied since work of Plücker (1835), Kirkman (1846) and Steiner (1853), but, before the Theorem was proved, there was not even known if any single Steiner system with $r>5$ exists. See here for a related resent result.

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

Go to the list of all theorems

Replica prediction holds for the limiting independence ratio in random regular graphs

You need to know: Graph, independent set in a graph, maximum independent set, d-regular graph, probability, selection uniformly at random, convergence in probability.

Background: The independence ratio $\text{IR}(G)$ of n-vertex graph G is the size of its maximum independent set divided by n. For positive integers $n,d$ with $nd$ even, let $G_{n,d}$ denote the uniformly random d-regular graph on n vertices, sampled as follows: start with n isolated vertices each equipped with d labelled half-edges, and form the graph by taking a uniformly random matching on the $nd$ half-edges. For fixed d, let $\text{IR}_n=\text{IR}(G_{n,d})$ .

For positive integer d, consider functions $\lambda_d(q)=q\frac{1-(1-q)^{d-1}}{(1-q)^d}$ , $\alpha_d(q)=q\frac{1-q+dq/(2\lambda_d(q))}{1-q^2(1-1/\lambda_d(q))}$ , and $f_d(q)=-\log\left[1-q\left(1-\frac{1}{\lambda_d(q)}\right)\right]-\left(\frac{d}{2}-1\right)\log\left[1-q^2\left(1-\frac{1}{\lambda_d(q)}\right)\right]-\alpha_d(d)\log \lambda_d(q)$ . Let $q^*(d)$ be the largest $q \leq 2(\log d)/d$ such that $f_d(q)=0$ , and let $\alpha^*(d)=\alpha_d(q^*(d))$ .

The Theorem: On 17th October 2013, Jian Ding, Allan Sly, and Nike Sun submitted to arxiv a paper in which they proved the existence of constant $d_0$ such that for all $d\geq d_0$ the independence ratio $\text{IR}_n$ of the random d-regular graph $G_{n,d}$ converges in probability to $\alpha^*(d)$ .

Short context: Determining the size of maximum independent set in random d-regular graph is not only a problem interesting in its own, but also has connection to statistical physics. In fact, the Theorem, including explicit formula for $\alpha^*(d)$ , has been derived in 2005 using non-rigorous analysis with physical origin (called replica symmetry breaking heuristics). The Theorem confirms this prediction rigorously.

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

Go to the list of all theorems

There exist infinite families of regular bipartite Ramanujan graphs of every degree d>=3

You need to know: Graph, bipartite graph, d-regular graph, adjacency matrix of a graph, eigenvalue of a matrix, limits.

Background: Let G be a d-regular bipartite graph and let A be its adjacency matrix. It is known that $d$ and $-d$ are always eigenvalues of A, which are called the trivial eigenvalues. We say that a d-regular bipartite graph is Ramanujan if all of its nontrivial eigenvalues lie between $-2\sqrt{d-1}$ and $2\sqrt{d-1}$ .

The Theorem: On 15th April 2013, Adam Marcus, Daniel Spielman, and Nikhil Srivastava submitted to arxiv a paper in which they proved that for every $d\geq 3$ there exists an infinite sequence of d-regular bipartite Ramanujan graphs.

Short context: Ramanujan graphs have various good properties, like being sparse but “highly connected”. Infinite families of d-regular Ramanujan graphs have been constructed by many authors, but, before 2013, such families where known to exist only if $d-1$ is a power of a prime number. The Theorem proves the existence of infinitely many d-regular bipartite Ramanujan graphs for every degree $d\geq 3$ .

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

Go to the list of all theorems