epsilon)

You need to know: Graph, isomorphic graphs, subgraph.

Background: A graph G is called H-free, if it does not have a subgraph isomorphic to H. Let $T:{\mathbb R}\to{\mathbb R}$ be a function defined by the rules (i) $T(1)=2$ , (ii) $T(n)=2^{T(n-1)}$ for $n=2,3,\dots$ , and (iii), for all real x, $T(x)=T(\bar{x})$ , where $\bar{x}$ is the least positive integer such that $x \leq \bar{x}$ .

The Theorem: On 10th January 2010, Jacob Fox submitted to the Annals of Mathematics a paper in which he proved the following result. For each $\epsilon>0$ and graph H on h vertices there is a $\delta=\delta(\epsilon,H)>0$ such that every graph on n vertices with at most $\delta n^h$ copies of H can be made H-free by removing at most $\epsilon n^2$ edges. Moreover, one can choose $\delta=T(5h^4\log \epsilon^{-1})^{-1}$ .

Short context: The statement of the Theorem without “moreover” part is famous graph removal lemma proved by Erdös, Frankl, and Rödl in 1986. It has many applications in graph theory and theory of algorithms. However, from their proof one can only take $\delta \approx T(P(\epsilon^{-1}))^{-1}$ for some polynomial P. The Theorem establishes the graph removal lemma with better dependence of $\delta$ from $\epsilon$ .

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

Go to the list of all theorems

The density Hales-Jewett theorem holds with an explicit bound

You need to know: Let ${\mathbb N}$ be the set of positive integers $\{1,2,3,\dots\}$ , big O notation.

Background: For positive integers k,n, let $[k]=\{1,2,\dots,k\}$ and let $[k]^n$ be the set of vectors $x=(x_1, \dots, x_n)$ such that each $x_i\in[k]$ . Let $y=(y_1, \dots, y_n)$ be a vector such that each $y_i$ either belongs to $[k]$ or equal to the wildcard value *. Assume that at least one coordinate of y takes the wildcard value *. For $j=1,2,\dots, k$ , let $y^j \in [k]^n$ be a vector obtained from y by setting all the wildcards * equal to j. The set $y^1, y^2, \dots, y^n$ is called a combinatorial line. Let $A:{\mathbb N} \times {\mathbb N} \to {\mathbb N}$ be a function such that $A(k,1)=2$ for all k, $A(1,n)=2n$ for all n, and $A(k,n) = A(k-1, A(k,n-1))$ for all $k, n>1$ .

The Theorem: On 20th October 2009, a large group of mathematicians submitted to arxiv a paper in which they proved the following result. For every positive integer k and every real number $\delta>0$ , there exists a positive integer $N=N(k,\delta)$ such that if $n\geq N$ and A is any subset of $[k]^n$ with at least $\delta k^n$ elements, then A contains a combinatorial line. Moreover, one may take $N(3,\delta) = A(3,O(1/\delta^2))$ and $N(k, \delta) = A(k+1,O(1/\delta))$ for $k \geq 4$ .

Short context: In 1975, Szemerédi proved that for any $k\in {\mathbb N}$ and any $\delta > 0$ , there exists a positive integer $M = M(k, \delta)$ such that every subset of the set $\{1, 2, \dots ,M\}$ of size at least $\delta M$ contains an arithmetic progression of length k. In 1991, Furstenberg and Katznelson proved the statement of the Theorem without “moreover” part, and called it “the density Hales-Jewett theorem”. This theorem greatly generalises (and easily implies) the Szemerédi theorem. However, the proof of Furstenberg and Katznelson does not imply any explicit algorithm how to actually compute $N=N(k,\delta)$ given $k$ and $\delta$ . The Theorem provides such an algorithm. It also has much simpler proof. It is proved by a large group of mathematicians in an online discussion, which is called a Polymath project.

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

Go to the list of all theorems

The threshold conjecture of Turán properties for random graphs is true

You need to know: Graph, notation $K_n$ for complete graph on n vertices, notations $v(H)$ and $e(H)$ for the number of vertices and edges in graph H, respectively.

Background: For a graph $F$ with $e(F)\geq 1$ and $v(F)\geq 3$ , let $m(F)$ be the maximum value of $\frac{e(H)-1}{v(H)-2}$ over all subgraphs H of F with $v(H)\geq 3$ . We say that a graph is F-free if it does not contain a copy of a graph F as a subgraph. For graph G, we write $\text{ex}(G, F)$ for the maximal number of edges that an F-free subgraph of G may have. Number $\pi(F)=\lim\limits_{n\to\infty}\frac{ex(K_n,F)}{e(K_n)}$ is known as Turán density of graph F. The Erdős-Renyi graph $G(n,p)$ is a random graph with n vertices, such that every possible edge is included independently with probability $p=p(n)$ .

The Theorem: On 16th October 2009, Mathias Schacht submitted to the Annals of Mathematics a paper in which he proved that for every graph $F$ with $e(F)\geq 1$ and $v(F)\geq 3$ and every $\epsilon>0$ , there exists $C=C(\epsilon)>0$ such that for every sequence of probabilities $q_n \geq Cn^{-1/m(F)}$ , we have $\lim\limits_{n\to\infty} P\left[\text{ex}(G(n,q_n),F) \leq \left(\pi(F)+\epsilon\right)e(G(n,q_n))\right]=1$ .

Short context: Function $\text{ex}(G, F)$ was first studied by Mantel, Erdős, and Turán. In particular, Turán determined in 1941 $\text{ex}(K_n, K_k)$ for all integers n and k. For general graph G, it is known that $\text{ex}(G, F) \geq \pi(F)e(G)$ . The Theorem proves that if G is a random graph, then the opposite inequality $\text{ex}(G, F) \leq (\pi(F)+\epsilon)e(G)$ holds with high probability. It confirms a conjecture of Kohayakawa, Łuczak, and Roedl made in 1997.

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

Go to the list of all theorems

The critical bias for the Hamiltonicity Maker-Breaker game is (1+o(1))n/log n

You need to know: Graph, complete graph, Hamilton cycle in a graph, logarithm $\log$ , small o notation.

Background: In the biased (1 : b) Hamiltonicity Maker-Breaker game, the players, called Maker and Breaker, take turns in claiming unoccupied edges of complete graph $K_n$ on n vertices. Maker claims 1 edge in his turn, Breaker answers by claiming b edges. Maker wins if she can construct a Hamilton cycle from the edges she have chosen.

The Theorem: On 15th September 2009, Michael Krivelevich submitted to arxiv a paper in which he proved that Maker has a strategy to win the (1 : b) Hamiltonicity game on $K_n$ in at most $14n$ moves, for every $b \leq \left(1-\frac{30}{\log^{1/4}n}\right)\frac{n}{\log n}$ , for all large enough n.

Short context: The research on biased Hamiltonicity games has a long history, starting from 1978 paper of Chvátal and Erdös, who showed that the Maker wins for large n if $b=1$ (in 2009, Hefetz and Stich proved that Maker can win in just n+1 rounds, which is optimal). In general, the critical bias $b^*(n)$ is the maximum possible value of b for which Maker still wins the (1 : b) game played on $K_n$ . Chvátal and Erdös proved that $b^*(n) \leq \left(1+o(1)\right)\frac{n}{\log n}$ . Many authors proved better and better lower bounds, culminating in the Theorem which implies that $b^*(n) \geq \left(1+o(1)\right)\frac{n}{\log n}$ , and hence equality holds.

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

Go to the list of all theorems

For large n, if set I of n-element permutations is k-intersecting, then its size is at most (n-k)!

You need to know: Notation $n!$ for $1 \cdot 2 \cdot \dots \cdot n$ , notation $|I|$ for the number of elements in finite set I, notation $[n]$ for the set $\{1,2,\dots,n\}$ .

Background: A permutation of $[n]$ is a function $\sigma:[n] \to [n]$ such that $\sigma(i) \neq \sigma(j)$ if $i\neq j$ . Let $S_n$ be the set of all permutations of $[n]$ . We say that two permutations $\sigma, \tau \in S_n$ k-intersect if there exist distinct $i_1, i_2,\dots i_k \in [n]$ such that $\sigma(i_t) = \tau (i_t)$ for $t = 1, 2,\dots,k$ . A subset $I \subset S_n$ is said to be k-intersecting if any two permutations in I k-intersect.

The Theorem: On 9th March 2009, David Ellis, Ehud Friedgut, and Haran Pilpel submitted to the Journal of the AMS a paper in which they proved that for any positive integer k, and any n sufficiently large depending on k, if $I \subset S_n$ is k-intersecting, then $|I| \leq (n-k)!$ .

Short context: Let us fix $\sigma \in S_n$ , fix $i_1, i_2,\dots i_k \in [n]$ , and let I be the set of all $\tau \in S_n$ such that $\sigma(i_t) = \tau (i_t)$ for $t = 1, 2,\dots,k$ . Then I is k-intersecting and $|I|=(n-k)!$ . If $n\leq 2k$ , we can construct large k-intersecting sets. However, the theorem states that if n sufficiently large depending on k, the construction above is optimal. The authors also proved that equality $|I|=(n-k)!$ holds only for the construction described above. This confirms conjecture of Frankl and Deza made in 1977.

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 n)^o(1))-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 4th March 2009, Boaz Barak, Anup Rao, Ronen Shaltiel, and Avi Wigderson submitted to the Annals of Mathematics a paper in which they proved the existence of absolute constants $\epsilon>0$ and $n_0$ such that there is an explicit construction of a $2^{2^{{(\log \log n)}^{1-\epsilon}}}$ -Ramsey graph over $n$ vertices for every integer $n>n_0$ .

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 2009, the best explicit construction was achieved in 1981 by Frankl and Wilson, who constructed k-Ramsey $2^n$ -vertex graphs for $k \approx 2^{\sqrt{\log n}}$ . Because $2^{2^{{(\log \log n)}^{1-\epsilon}}}=2^{(\log n)^{o(1)}}$ , the Theorem significantly improves this result. In a later work, Cohen presented an even better $2^{(\log \log n)^c}$ -Ramsey construction.

Links: The original paper is available here.

Go to the list of all theorems

The hypergraph Ramsey numbers r_3(s,n) are at most 2^(n^(s-2) log n)

You need to know: Factorial $n!=1\cdot 2 \cdot \dots \cdot n$ , logarithm $\log$ , limit, $o(1)$ notation.

Background: The hypergraph Ramsey number $r_k(s, n)$ is the minimum N such that every red-blue colouring of the unordered k-tuples of an N-element set contains a red set of size s or a blue set of size n, where a set is called red (blue) if all k-tuples from this set are red (blue).

The Theorem: On 27th August 2008, David Conlon, Jacob Fox, and Benny Sudakov submitted to arxiv a paper in which they proved that (i) for fixed $s \geq 4$ and sufficiently large n, $\log r_3(s,n) \leq \left(\frac{s-3}{(s-2)!}+o(1)\right)n^{s-2}\log n$ , and (ii) there is a constant $c>0$ such that $\log r_3(s,n) \geq c s n \log \left(\frac{n}{s}+1\right)$ for all $4 \leq s \leq n$ .

Short context: It follows from famous 1929 Ramsey Theorem that numbers $r_k(s, n)$ exists and finite, and, since that, finding upper and lower bounds for them is an active area of research in combinatorics, see here for a progress in case $k=2$ , $s=n$ . For the upper bound, Erdős and Rado proved in 1952 that $\log r_3(s,n)$ is at most $c n^{2s-4}/\log^{2s-6}n$ . Part (i) of the Theorem improves this by factor $n^{s-2}$ , ignoring $\log n$ factors. For the lower bound, Erdős and Hajnal showed in 1972 that $\log r_3(4, n) > c n$ for some $c>0$ , and conjectured that in fact $\lim\limits_{n\to\infty}\frac{r_3(4, n)}{n}=\infty$ . Part (ii) of 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 cost L_n of the mean-field TSP on n-vertex graph converges to 2.04…

You need to know: Graph, complete graph, limits, integration, notation $P$ for probability, random variable, distribution.

Background: In a complete graph on n vertices, let each edge $e$ be assigned independent random cost $C_e$ from a fixed distribution $\mu$ on the non-negative real numbers, such that $\lim\limits_{t \to 0^+} \frac{P(C_e<t)}{t} = 1$ . Let $L_n$ be the minimum sum of the edge costs of a cycle that visits each vertex precisely once. For any $x>0$ , let $y=y(x)$ be the unique real number such that $\left(1+\frac{x}{2}\right)e^{-x} + \left(1+\frac{y}{2}\right)e^{-y}=1$ . Let $L^*=\frac{1}{2}\int_0^\infty y(x)dx = 2.0415...$ .

The Theorem: On 3rd April 2008, Johan Wästlund submitted to Acta Mathematica a paper in which he proved that for any $\epsilon>0$ , $\lim\limits_{n\to \infty}P\left[\left|L_n - L^*\right|>\epsilon\right] = 0.$

Short context: Computing the minimum sum of the edge costs of a cycle that visits each vertex of a graph is a famous and important problem known as travelling salesman problem (TSP). A model in which the edge costs are random, chosen independently from a fixed distribution, is known as the mean field model of distance. The Theorem finds the limit of the optimal cost of the mean-field TSP for a general class of distributions, which contains, for example, uniform distribution on $[0, 1]$ or exponential with mean $1$ .

Links: The original paper is available here.

Go to the list of all theorems

The size of every Kakeya set in F^n, where F is a finite field, is at least C_n|F|^n

You need to know: Field, finite field, vector space over a field, dimension of a vector space. In addition, you need the concept of Hausdorff dimension of subsets of Euclidean space ${\mathbb R}^n$ for the context section.

Background: Let ${\mathbb F}$ be a finite field with $|{\mathbb F}|$ elements, and let ${\mathbb F}^n$ be a vector space over ${\mathbb F}$ of dimension n. A Kakeya set in ${\mathbb F}^n$ is a subset $K \subset {\mathbb F}^n$ such that for every $x\in {\mathbb F}^n$ there exists a point $y\in {\mathbb F}^n$ such that the set $L=\{y+a\cdot x\,|\,a\in {\mathbb F}\}$ (called a line) is contained in K.

The Theorem: On 16th March 2008, Zeev Dvir submitted to arxiv a paper in which he proved that the size of every Kakeya set in ${\mathbb F}^n$ is at least $C_n \cdot |{\mathbb F}|^{n}$ , where $C_n$ is a constant that depends only on $n$ .

Short context: Famous Kakeya conjecture states that every compact set $K \subset {\mathbb R}^n$ , which contains a line segment of unit length in every direction, must have Hausdorff dimension equal to n. This conjecture has connections to problems in number theory, harmonic analysis, and the analysis of partial differential equations, but remains open for all $n>2$ . In 1999, Wolff suggested to study its finite field analogue. The Theorem resolves the Kakeya conjecture is finite fields.

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

Go to the list of all theorems

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