The number of n-faces genus-g triangulations if g/n converges to a constant

You need to know: Basic topology, homeomorphism, topological surface, orientable surface, genus of a surface, $o(n)$ notation.

Background: A (two-dimensional, orientable) triangulation $T$ is a way to glue together a collection of oriented triangles, called the faces, along their edges in a connected way that matches the orientations. If the number of triangles is finite, then $T$ is homeomorphic to an orientable topological surface $S$ . Let us define the genus of $T$ as the genus of $S$ . The triangulation $T$ is called rooted if it has a distinguished oriented edge called the root edge. Let $\tau(n,g)$ be the number of rooted triangulations with $n$ faces and genus $g$ .

Let $\lambda_c=\frac{1}{12\sqrt{3}}$ . For any $\lambda\in(0,\lambda_c]$ , let $h\in (0,\frac{1}{4}]$ be such that $\lambda = \frac{h}{(1+8h)^{3/2}}$ , and let
$d(\lambda) = \frac{h\log\frac{1+\sqrt{1-4h}}{1-\sqrt{1-4h}}}{(1+8h)\sqrt{1-4h}}$ . For any $\theta\in(0,\frac{1}{2})$ , let $\lambda(\theta)$ be the unique solution to the equation $d(\lambda)=\frac{1-2\theta}{6}$ , and let $f(\theta) = 2 \theta \log \frac{12\theta}{e} + \theta \int_2^{1/\theta} \log\frac{1}{\lambda(1/t)}dt, \, 0<\theta<\frac{1}{2}$ . Also, let $f(0)=\log 12\sqrt{3}$ and $f(1/2)=\log\frac{6}{e}$ .

The Theorem: On 1st February 2019, Thomas Budzinski and Baptiste Louf submitted to arxiv a paper in which that proved that for any sequence $g_n$ such that $0 \leq g_n \leq \frac{n+1}{2}$ for every $n$ and $\lim_{n\to\infty}\frac{g_n}{n}=\theta \in [0,\frac{1}{2}]$ , one has $\tau(n,g_n) = n^{2 g_n} \exp(f(\theta)n + o(n)) \,\text{as}\, n\to\infty$ .

Short context: Triangulations are important in many applications, for example, as finite representations of a surface to a computer, or in the theory of random surfaces. In the last application, it is important to understand how a uniformly random triangulation looks like, and, for this, we need to count triangulations with various properties. In 1986, Bender and Canfield established the asymptotic growth of $\tau(n,g)$ when $n\to\infty$ and $g$ is fixed. However, the important case when $n$ and $g$ both go to infinity remained open. The Theorem estimates $\tau(n,g)$ up to sub-exponential factors in the case when the ratio $g/n$ converges to a constant.

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

Go to the list of all theorems

For c<1/4, the chromatic number of G(n,1/2) is not concentrated on n^c consecutive values

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.

The Theorem: On 27th June 2019, Annika Heckel submitted to arxiv and the Journal of the AMS a paper in which she proved that for any constant $c<\frac{1}{4}$ , there is no sequence of intervals of length $n^c$ which contain $\chi(G(n,1/2))$ with high probability.

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 2003, Achlioptas and Naor proved that if $p=\frac{d}{n}$ for constant d, then, 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$ . The Theorem states that if $p=\frac{1}{2}$ is a constant, then $\chi(G(n,1/2))$ is not concentrated in any interval of finite length. This answers the 1992 question of Paul Erdős.

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

Go to the list of all theorems

Mason’s ultra-log-concavity conjecture for independent sets of matroids is true

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 M 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$ . Let $I_k(M)$ be the number of sets $A \in I$ with $|A|=k$ .

The Theorem: On 5th November 2018, Petter Brändén and June Huh, and, independently, Nima Anari, Kuikui Liu, Shayan Oveis Gharan and Cynthia Vinzant submitted to arxiv a paper in which they proved that for any n-element matroid M, and any positive integer k, $I_k(M)^2 \geq \frac{k+1}{k}\frac{n-k+1}{n-k}I_{k-1}(M)I_{k+1}(M)$ .

Short context: In 1972, Mason made three conjectures about sequence $I_k(M)$ , in the increasing order of strength: (i) $I_k(M)^2 \geq I_{k-1}(M)I_{k+1}(M)$ , (ii) $I_k(M)^2 \geq \frac{k+1}{k}I_{k-1}(M)I_{k+1}(M)$ , and (iii) $I_k(M)^2 \geq \frac{k+1}{k}\frac{n-k+1}{n-k}I_{k-1}(M)I_{k+1}(M)$ . Property (i) is called log-concavity, while (iii) is called ultra log-concavity. In 2015, Adiprasito, Huh, and Katz proved part (i). In June 2018, Huh, Schröter and Wang proved (ii). Finally, the Theorem proves (iii).

Links: Free arxiv version of the original paper is here (see also here and here), journal version is here.

Go to the list of all theorems

K_d,d maximises the normalised number of q-colourings over all d-regular graphs

You need to know: Graph, proper colouring of vertices of a graph, bipartite graph, complete bipartite graph, degree of a vertex in a graph, d-regular graph (graph in which all vertices have the same degree d).

Background: Let $c_q(G)$ be the number of proper colourings of graph G. Also, let $|V(G)|$ denote the number of vertices of G. Finally, let $K_{d,d}$ denote the complete bipartite graph on $2d$ vertices.

The Theorem: On 25th September 2018, Ashwin Sah, Mehtaab Sawhney, David Stoner, and Yufei Zhao submitted to arxiv a paper in which they proved that for every d-regular graph G and every positive integer q, one has $c_q(G)^{1/|V(G)|}\leq c_q(K_{d,d})^{1/2d}$ .

Short context: Given graph G, quantity $c_q(G)^{1/|V(G)|}$ is called the normalised number of q-colourings of G. This normalisation is a natural choice, because replacing G by a disjoint union of copies of itself does not change the quantity $c_q(G)^{1/|V(G)|}$ . In 2004, Galvin and Tetali initiated the study of the following question: given positive integers d and q, what d-regular graph G maximises $c_q(G)^{1/|V(G)|}$ ? The Theorem proves that the answer is $K_{d,d}$ .

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

Go to the list of all theorems

The Sensitivity Conjecture is true

You need to know: For the Theorem: Graph, induced subgraph, degree of a vertex of a graph, notation $\Delta(H)$ for the maximum degree of graph H. In addition, you may want to go the original paper (or online) and learn what is the Sensitivity Conjecture to fully appreciate the context.

Background: The n-dimensional hypercube graph is the graph $Q^n$ , whose vertex set consists of vectors $(x_1, x_2, \dots, x_n)$ such that each $x_i$ is either $0$ or $1$ , and two vectors are adjacent if they differ in exactly one coordinate.

The Theorem: On 1st July 2019, Hao Huang submitted to arxiv a paper in which he proved that for every integer $n\geq 1$ , and every $(2^{n-1}+1)$ -vertex induced subgraph H of $Q^n$ , one has $\Delta(H) \geq \sqrt{n}$ .

Short context: The inequality $\Delta(H) \geq \sqrt{n}$ in the Theorem is the best possible, in sense that it is tight when n is a perfect square. The Theorem confirms a conjecture of Gotsman and Linial made in 1992, who proved that their conjecture, if true, would imply the celebrated Sensitivity Conjecture, one of the famous conjectures in theoretical computer science. The Theorem confirms the Gotsman-Linial conjecture and hence the Sensitivity Conjecture.

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

Go to the list of all theorems

The Hedetniemi’s conjecture is false

You need to know: Graph, finite simple graph, vertex set $V(G)$ and edge set $E(G)$ of graph G, notation $S \times T$ for the set of pairs $(s,t)$ where $s \in S$ and $t\in T$ , chromatic number $\chi(G)$ of graph G.

Background: The tensor product $G\times H$ of finite simple graphs G and H is the graph with vertex set $V (G) \times V (H)$ , such that pairs $(g,h)$ and $(g',h')$ are adjacent if and only if $\{g,g'\}\in E(G)$ and $\{h,h'\}\in E(H)$ .

The Theorem: On 6th May 2019, Yaroslav Shitov submitted to arxiv a paper in which he proved the existence of finite simple graphs G and H such that $\chi(G \times H) < \min\{\chi(G), \chi(H)\}$ .

Short context: It is easy to see that $\chi(G \times H) \leq \min\{\chi(G), \chi(H)\}$ for all graphs G,H. The classical conjecture of Hedetniemi, made in 1966, predicted that the equality holds for all G and H. The conjecture attracted a lot of attention, and has been proved in a number of special cases. The Theorem, however, states that in general this conjecture is false.

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

Go to the list of all theorems

The h*-bound for the minimum number of triangles in n-vertex e-edge graph is tight if n>n0(a), e<n(n-1)/2-an^2

You need to know: Set ${\mathbb N}$ of positive integers, graph, clique in a graph, triangle (3-vertex clique).

Background: Let $n>0$ and $0<e\leq \frac{n(n-1)}{2}$ be integers. Let $g_3(n,e)$ be the minimum number of triangles a graph with n verities and e edges can have. We have an upper bound $g_3(n,e)\leq h^*(n,e)$ , called “the h*-bound”, where $h^*(n,e)$ is the explicit function.

The definition of $h^*(n,e)$ (which you may skip) is: for any integer $r>0$ , we can write $n=d_rr+b_r$ for integers $d_r$ and $0\leq b_r<r$ . Define $t_r(n)=\frac{n(n-1)}{2}-b_r\frac{d_r(d_r+1)}{2}-(r-b_r)\frac{d_r(d_r-1)}{2}$ . Let $k=k(n,e)$ be the unique positive integer with $t_{k-1}(n)<e\leq t_k(n)$ . Let $a^*=a^*(n,e)$ be the unique integer vector $a^*=(a_1^*,\dots, a_k^*)$ such that (i) $a_k^*=\min\{a\in{\mathbb N}:a(n-a)+t_{k-1}(n-a)\leq e\}$ and (ii) $a_1^*+\dots+a_{k-1}^*=n-a_k^*$ and $a_1^*\geq \dots \geq a_{k-1}^* \geq a_1^*-1$ . Then let $m^*=\sum\limits_{1\leq i < j \leq k}a_i^*a_j^*-e$ , and finally $h^*(n,e)=\sum\limits_{1\leq h<i < j \leq k}a_h^*a_i^*a_j^*-m^*\sum\limits_{i=1}^{k-2}a_i^*$ .

The Theorem: On 2nd December 2017, Hong Liu, Oleg Pikhurko, and Katherine Staden submitted to arxiv and the Forum of Mathematics, Pi a paper in which they proved that for any $\epsilon>0$ , there exists $n_0=n_0(\epsilon)>0$ such that for all positive
integers $n \geq n_0$ and $e\leq \frac{n(n-1)}{2}-\epsilon n^2$ , we have that $g_3(n,e)=h^*(n,e)$ .

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 $t_r(n)$ 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. In 2016, Reiher proved a lower bound on $g_r(n,e)$ , which, together with the known upper bound, allows to estimate $g_r(n,e)$ asymptotically in the limit. The Theorem establishes the exact value of $g_r(n,e)$ in the case $r=3$ , n large, and $e\leq {{n}\choose{2}}-\epsilon n^2$ .

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

Go to the list of all theorems

The chromatic number of the plane is at least 5

You need to know: Distance between points on the plane.

Background: The chromatic number of the plane is the minimum number of colours that are needed to colour the plane so that no two points at distance exactly 1 from each other have the same colour.

The Theorem: On 8th April 2018, Aubrey de Grey submitted to arxiv a paper in which he proved that the chromatic number of the plane is at least 5.

Short context: The problem of determining the chromatic number of the plane was posed by Nelson in 1950, and is one of the beautiful problems that are easy to understand but difficult to solve. Because the vertices of any equilateral triangle with side length 1 should receive different colours, at least 3 colours in needed, and it is not much harder to see that in fact at least 4 colours is required. As observed by Isbell also in 1950, 7 colours suffices. These trivial bounds have not been improved for almost 70 years, until de Grey proved that 4 colours are not enough and at least 5 is needed.

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

Go to the list of all theorems

Every set A of natural numbers with positive density contains B+C for some infinite sets B and C

You need to know: Notation ${\mathbb N}$ be the set of positive integers, finite and infinite sets, notation $|S|$ for the number of elements in finite set S, limit superior $\limsup$ .

Background: Let $A\subset {\mathbb N}$ be any set of natural numbers. We say that A has positive upper density if $\limsup\limits_{n\to\infty}\frac{|A \cap \{1,2,\dots,n\}|}{n} > 0$ . The sum of sets $B \subset {\mathbb N}$ and $C \subset {\mathbb N}$ is $B+C=\{b+c: b\in B, c\in C\}$ .

The Theorem: On 1st March 2018, Joel Moreira, Florian Richter, and Donald Robertson submitted to arxiv a paper in which they proved that any set $A\subset {\mathbb N}$ of positive upper density contains $B+C$ , where B and C are infinite subsets of ${\mathbb N}$ .

Short context: The infinite version of famous Ramsey’s 1929 Theorem implies that if integers are partitioned into finitely many sets, then at least one of these sets contains $B+C$ for infinite sets B and C. The Theorem proves a density version of this statement, which was known as the Erdős sumset conjecture.

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

Go to the list of all theorems

The cap set conjecture is true: the size of any cap set in F_3^n is o(2.756^n)

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

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 30th May 2016, Jordan Ellenberg and Dion Gijswijt submitted to arxiv a paper in which they proved that if $A \subseteq {\mathbb F}_3^N$ is a cap set, then $|A|=o(2.756^n)$ .

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 predicted the existence of constant $c<3$ such that $|A|<c^n$ for every cap set $A \subseteq {\mathbb F}_3^n$ . The Theorem confirms this conjecture, building on an earlier similar result for subsets of ${\mathbb Z}_4^n$ . Before 2016, the best upper bound was $|A|\leq C\frac{3^n}{n^{1+\epsilon}}$ , see here.

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

Go to the list of all theorems