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

Approximation ratio 3/2 for the metric TSP is not optimal

You need to know: Algorithms and their running time, polynomial algorithm, probabilistic algorithm, basic graph theory, complete graph, hamiltonian cycle.

Background: The metric travelling salesman problem (TSP) asks to find a hamiltonian cycle (also called TSP tour) of minimum weight in a compete graph with non-negative edge weights.

The Theorem: On 2nd July 2020, Anna Karlin, Nathan Klein and Shayan Gharan submitted to arxiv a paper in which they proved that there exists a constant $\epsilon > 0$ and a randomized algorithm that outputs a TSP tour with expected weight at most $\frac{3}{2}-\epsilon$ times the weight of the optimal tour. In fact, one can take $\epsilon=10^{-36}$ .

Short context: The TSP is one of the most-studied problems in the theory of algorithms. In 1970-th, Christofides and Serdyukov developed a polynomial time algorithm which finds a hamiltonian cycle of weight at most $\frac{3}{2}$ times the optimal one. Because the Christofides-Serdyukov algorithm has been unimproved for over 40 years, some people started to conjecture that the approximation ratio $\frac{3}{2}$ is optimal for polynomial-time algorithms. The Theorem disproves this conjecture.

Links: The free version of the original paper is available here.

Go to the list of all theorems

Amir’s conjecture for random walks on groups is true

You need to know: Group, set of generators, finitely generated group, basic probability theory, independent identically distributed (i.i.d.) random variables.

Background: Let $G$ be an infinite group with finite generating set $S$ . Let $S^{-1}=\{g \in G\,|\,g^{-1}\in S\}$ , and let $|g|$ be the smallest integer $k\geq 0$ such that $g\in G$ has representation $g=\prod_{i=1}^k s_i$ with each $s_i \in S \cup S^{-1}$ . A symmetric finitely supported probability measure on $G$ is a function $\mu:G\to[0,1]$ such that set $\{g \in G\,|\,\mu(g)>0\}$ is finite, $\sum_{g\in G} \mu(g)=1$ , and $\mu(g^{-1})=\mu(g)$ for all $g \in G$ . Let $X_1, X_2, \dots$ be a sequence of i.i.d. random variables with distribution $\mu$ , that is, such that ${\mathbb P}[X_i=g]=\mu(g)$ for all $g\in G$ and all $i$ . A random walk on $G$ with step distribution $\mu$ is the sequence $W_1,W_2,\dots$ given by $W_n=\prod_{i=1}^n X_i$ . A speed function of random walk $W_n$ is $L_\mu(n) = {\mathbb E}[|W_n|] = \sum_{g\in G}|g|{\mathbb P}[W_n=g]$ . Its entropy is $H_\mu(n) = - \sum_{g\in G}{\mathbb P}[W_n=g]\log{\mathbb P}[W_n=g]$ . The exponent of a function $f$ is $\lim_{n\to\infty} \frac{\log f(n)}{\log n}$ , provided that the limit exists.

The Theorem: On 27th October 2015, Jérémie Brieussel and Tianyi Zheng submitted to arxiv a paper in which they proved that for any $\gamma\in[1/2,1]$ and $\theta\in[1/2,1]$ satisfying $\theta \leq \gamma \leq \frac{1}{2}(\theta+1)$ , there exist a finitely generated group $G$ and a symmetric probability measure $\mu$ of finite support on $G$ , such that the random walk on $G$ with step distribution $\mu$ has speed exponent $\gamma$ and entropy exponent $\theta$ .

Short context: The main research directions in studying random walks on groups are (i) given a group, establish properties of random walk on it, and, conversely (ii) given properties of a random walk, find if there exists a group with such random walk. The Theorem contributes to direction (ii). It confirms a conjecture of Amir who proved the same result for $\gamma,\theta\in[3/4,1]$ .

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

Go to the list of all theorems

The size of subset of {1,…,N} without distinct degree polynomial progressions is O(N/(log log N)^c)

You need to know: Polynomial, degree of a polynomial, notation ${\mathbb Z}[y]$ for the set of polynomials in 1 variable with integer coefficients, notation $[N]$ for the set $\{1,2,\dots,N\}$ .

Background: Let $P=(P_1, \dots, P_m)$ be a finite set of polynomials $P_i \in {\mathbb Z}[y]$ . For integer $N>0$ , let $r_P(N)$ be the size of the largest subset of $[N]$ containing no subset of the form $x, x+P_1(y), \dots, x+P_m(y)$ with $y\neq 0$ .

The Theorem: On 1st September 2019, Sarah Peluse submitted to arxiv a paper in which she proved that if all polynomials $P_i$ in $P$ have distinct degrees and zero constant terms, then there exists a constant $c$ depending on $P_1, \dots, P_m$ such that
$r_P(N) \leq \frac{N}{(\log\log N)^c}$ .

Short context: Let $r_k(N)$ be the cardinality of the largest subset of $[N]$ which contains no nontrivial k-term arithmetic progressions. Famous Szemerédi’s theorem states that $\lim\limits_{N\to\infty}\frac{r_k(N)}{N}=0$ . In 2000, Gowers proved an explicit bound $r_k(N) < N(\log\log N)^{-c}$ for some constant $c=c(k)>0$ . In 1996, Bergelson and Leibman extended Szemerédi’s theorem to polynomial progressions and proved that $\lim\limits_{N\to\infty} \frac{r_P(N)}{N} = 0$ , if polynomials $P_i$ all have zero constant terms. The Theorem establishes an explicit upper bound on $r_P(N)$ , provided that all polynomials $P_i$ have distinct degrees.

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

An explicit construction of polynomials with optimal condition numbers

You need to know: Basic complex analysis, set ${\mathbb C}$ of complex numbers, absolute value $|z|$ of complex number z, polynomials in complex variable, root of a polynomial, derivative $P'(z)$ of polynomial $P(z)$ , binomial coefficients ${N\choose i}=\frac{N!}{i!(N-k)!}$ .

Background: For polynomial $P(z)=\sum_{i=0}^N a_i z^i$ with complex coefficients $a_i$ , its Weil norm is $||P|| = \sqrt{\sum_{i=0}^N {N\choose i}^{-1}|a_i|^2}$ , and its (normalised) condition number is $\mu(P) = \max\limits_{z \in {\mathbb C}: P(z)=0} \left(\sqrt{N}\frac{||P||(1+|z|^2)^{N/2-1}}{|P'(z)|}\right)$ .

The Theorem: On 4th March 2019, Carlos Beltrán, Ujué Etayo, Jordi Marzo, and Joaquim Ortega-Cerdà submitted to arxiv a paper in which they proved the existence a constant C and an explicit formula, which, given any integer $N>0$ , produces a polynomial $P_N$ of degree N such that $\mu(P_N) \leq C \sqrt{N}$ .

Short context: A fundamental problem in mathematics is numerical computation of roots of polynomials. Because in numerical studies the coefficients of polynomials are known only approximately, the central issue is to understand what effect on the roots has a slight perturbation of the coefficients. In 1993, Shub and Smale introduced the condition number $\mu(P)$ and observed that for polynomials with small $\mu(P)$ the root computation is stable with respect to the coefficients perturbations. They also proved that a random polynomial P of degree N has $\mu(P)\leq N$ with probability at least $1/2$ , and posed the problem to construct an example of such polynomials explicitly. The Theorem solves this problem. The bound $\mu(P_N) \leq C \sqrt{N}$ is the best possible up to a constant factor.

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

Go to the list of all theorems

The hot spots conjecture is true for Lip domains

You need to know: Euclidean plane ${\mathbb R}^2$ , orthonormal coordinate system, smooth (that is, differentiable) function in 2 variables, first and second order partial derivatives, notation $\Delta f = \frac{\partial^2 f}{\partial x_1^2}+\frac{\partial^2 f}{\partial x_2^2}$ , directional derivative $\frac{\partial f}{\partial n}$ for a vector n, normal vector, Lipschitz function.

Background: Let $\Omega \subset {\mathbb R}^2$ be a Lipschitz domain, that is, a bounded domain with boundary $\partial\Omega$ such that every $x \in \partial\Omega$ has a neighbourhood U such that $\partial\Omega \cap U$ is the graph of a Lipschitz function in some orthonormal coordinate system. A bounded, open, connected Lipschitz domain is called a Lip domain if it is given by $\Omega = \{(x1, x2): f_1(x_1)<x_2<f_2(x_1)\}$ , where $f_1$ , $f_2$ are Lipschitz functions with constant 1. The second Neumann eigenvalue $\mu_2=\mu_2(\Omega)$ is the smallest positive real number such that there exists a not identically zero, smooth function $u : \Omega \to {\mathbb R}$ that satisfies the equation $\Delta u =-\mu_2 \cdot u$ on $\Omega$ and the boundary condition $\left.\frac{\partial u}{\partial n}\right|_{\partial \Omega} \equiv 0$ at the smooth points of $\partial\Omega$ , where n denotes the outward pointing normal vector (see here for an equivalent definition of $\mu_2$ ). A function u that satisfies these conditions is called the second Neumann eigenfunction for $\Omega$ .

The Theorem: On 17th December 2001, Rami Atar, and Krzysztof Burdzy submitted to The Journal of the AMS a paper in which they proved that if $\Omega \subset {\mathbb R}^2$ is a Lip domain, then the second Neumann eigenfunction attains its extrema at the boundary of $\Omega$ .

Short context: The conjecture that the second Neumann eigenfunction attains its extrema at the boundary of $\Omega$ is known as the hot spot conjecture. In simple English, it states that if a flat piece of metal is given an initial heat distribution which then flows throughout the metal, then, after some time, the hottest point on the metal will lie on its boundary. The conjecture was proposed by Rauch in 1974. In 1999, Burdzy and Werner constructed a domain (with holes) for which the conjecture fails, but it still believed to be true for domains without holes. The Theorem confirms the conjecture for all Lip domains. In a later work, the conjecture has also been proved for all triangles.

Links: The original paper is available here.

Go to the list of all theorems

Kesten’s theorem holds for random Kronecker sequences on the torus T^d

You need to know: Matrix, determinant of a matrix, notation $AC$ for the image of set $C$ under linear transformation defined by matrix $A$ , notation $\times$ for direct product of sets, notation “ $x \mod 1$ ” for the real number $y\in[0,1)$ such that $x-y$ is an integer, notation ${\mathbb P}$ for the probability, selection uniformly at random.

Background: Let $d>0$ be an integer, $I=\{1,2,\dots,d\}$ , $T=[0,1)$ , and $T^d$ be set of vectors $x=(x_1, \dots, x_d)$ with $x_i \in T$ for every $i \in I$ . Let $U$ be the set of vectors $u=(u_1, \dots, u_d)$ such that $v_i\leq u_i \leq w_i$ for every $i \in I$ , where $v_i, w_i$ are fixed such that $0<v_i<w_i<1/2$ for every $i \in I$ . For each $u\in U$ , let $C_u$ be the set of vectors $y=(y_1, \dots, y_d)$ such that $|y_i|\leq u_i$ for every $i \in I$ . For a (small) $\eta>0$ , let $G_\eta$ be the set of $d\times d$ matrices with determinant $1$ and real entries $a_{ij}$ , such that $|a_{ii}-1|<\eta$ for all $i$ and $|a_{ij}|<\eta$ for all $i\neq j$ . Let $X=T^d \times T^d \times U \times G_\eta$ . For $\nu = (\alpha, x, u, A) \in X$ and integer $N>0$ , let $M(\nu, N)$ be the number of integers $1\leq m \leq N$ such that $(x+m\alpha) \mod 1 \in A C_u$ , and let $D(\nu, N)=M(\nu, N) - 2^d (\prod_{i=1}^d u_i) N$ .

The Theorem: On 19th November 2012 Dmitry Dolgopyat and Bassam Fayad submitted to arxiv a paper in which they proved that if $\nu$ is selected in $X$ uniformly at random, then, for all real $z$ , $\lim\limits_{N\to\infty}{\mathbb P}\left(\frac{D(\nu,N)}{(\ln N)^d}\leq z\right)=F(\rho_d z)$ , where $\rho_d$ is a constant depending only on $d$ , and $F(z)=\frac{\arctan(z)}{\pi}+\frac{1}{2}$ .

Short context: For every irrational $\alpha$ , it is known that sequence $\alpha, 2\alpha, \dots, m\alpha, \dots$ (called the Kronecker sequence) is uniformly distributed on $[0,1)$ , and the same is true for shifted sequence $x+\alpha, \dots, x+m\alpha, \dots$ . More formally, if $M(N)$ is the number of terms of this sequence (with $1\leq m\leq N$ ) belonging to some interval $[a,b) \subset [0,1)$ , then $\lim\limits_{N\to\infty}\frac{M(N)}{N}=b-a$ . Quantity $D(N)=M(N)-(b-a)N$ measures how fast this convergence happens. In 1962, Kesten established the limiting distribution of $D(N)$ , after appropriate scaling, provided that $x$ and $\alpha$ are selected at random. The Theorem establishes a multidimensional version of this result.

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

Go to the list of all theorems

Flat Littlewood polynomials exist

You need to know: Polynomials, degree of a polynomial, set ${\mathbb C}$ of complex numbers, absolute value $|z|$ of complex number $z$ .

Background: A polynomial $P(z)$ of degree n in complex variable z is called a Littlewood polynomial if $P(z) = \sum_{k=0}^n \epsilon_k z^k$ , where $\epsilon_k \in \{-1,1\}$ for all $0\leq k \leq n$ .

The Theorem: On 22nd July 2019, Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe and Marius Tiba submitted to arxiv and Annals of Mathematics a paper in which they proved the existence of constants $\Delta>\delta>0$ such that, for all $n\geq 2$ ,
there exists a Littlewood polynomial $P(z)$ of degree n with $\delta\sqrt{n} \leq |P(z)| \leq \Delta\sqrt{n}$ for all $z \in {\mathbb C}$ with $|z|=1$ .

Short context: Polynomials satisfying the condition of the Theorem are called flat polynomials, hence the Theorem states that flat Littlewood polynomials exist. It answers a question of Erdos from 1957, and confirms a conjecture of Littlewood made in 1966.

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