## Minimal Ramsey problems

Thanks to Anita Liebenau, I have recently been introduced to some very interesting questions in Ramsey theory and I have been working on them for the past few months in collaboration with various people. In my recent joint work with John Bamberg and Thomas Lesgourgues (Anita’s PhD student), that has just appeared on the arXiv, we have  proved an interesting new result in one of these problems. Before I discuss that, let’s look at some background in this post.

The well known fact that in any party of six people either at least three of them are mutual strangers or at least three of them are mutual acquaintances (see this or this), which serves as a nice introduction to Ramsey theory, can be written in graph theoretical terms as follows: any two colouring of the edges of the complete graph $K_6$ contains a monochromatic $K_3$. Let’s write this statement as $K_6 \longrightarrow (K_3)_2$, which we read as “ $K_6$ is $2$-Ramsey for $K_3$”.

We can generalise this notion to any two finite graphs $G$ and $H$; let’s write $G \longrightarrow (H)_r$ if any $r$-colouring of the edges of $G$ contains a monochromatic copy of $H$, and hence $G \longarrownot\longrightarrow (H)_r$ is a shorthand for the statement that here exists an $r$-colouring of the edges without a monochromatic $H$. Observe that if $G \longrightarrow (H)_r$ then for any graph $G'$ containing $G$ as a subgraph we have $G' \longrightarrow (H)_r$, or equivalently, if $G \longarrownot\longrightarrow (H)_r$ then for any subgraph $G'$ of $G$ we have $G' \longarrownot\longrightarrow (H)_r$. For example, here is a red/blue colouring of $K_6$ minus an edge that has no monochromatic triangles, thus showing that $K_6 - e \longarrownot\longrightarrow (K_3)_2$. This example in fact shows that the graph $K_6$ is minimal with respect to being $2$-Ramsey for $K_3$, since $K_6$ is $2$-Ramsey for $K_3$ but no proper subgraph of $K_6$ has this property.

In general, we say that a graph $G$ is $r$-Ramsey minimal for another graph $H$, if $G \longrightarrow (H)_r$ and for any proper subgraph $G'$ of $G$ we have $G' \longarrownot\longrightarrow (H)_r$. Let’s denote the set of all graphs $G$ that are $r$-Ramsey minimal for a graph $H$ by $\mathcal{M}_r(H)$. Most of the fundament problems in graph Ramsey theory can be seen as trying to understand this set for various graphs $H$. The classical result of Ramsey can be rephrased as:

Theorem 1. (Ramsey, 1930) The set $\mathcal{M}_r(H)$ is non-empty for any finite graph $H$.

The well studied $r$-colour Ramsey number of a graph $H$, denoted by $R_r(H)$ is simply the smallest number of vertices among all graphs in $\mathcal{M}_r(H)$. Determining, or even estimating, the number $R_2(K_k)$, which is denoted by $R(k)$, has been one of the central longstanding open problem in combinatorics. The work done towards resolving this has led to significant development in combinatorics.  It was shown by Erdős and Szekeres  in 1935 that $R(k) \leq 2^{2k}$, and in 1947 Erdős proved the lower bound of $R(k) \geq 2^{k/2}$ using a probabilistic argument that led to the creation of what we now call the probabilistic method in combinatorics. But, despite decades of research we still haven’t been able to improve the base of the exponents in these upper and lower bounds! For the most recent development on the upper bounds see this paper by Ashwin Sah.

Other parameters like the number of edges, chromatic number and maximum degree of graphs in $\mathcal{M}_r(H)$, have also been studied extensively. The question that I have been looking into is determining the smallest minimum degree in $\mathcal{M}_r(H)$, which is denoted by $s_r(H)$. In particular, the new result concerns $s_r(k) = s_r(K_k)$.

For any graph $H$, the graph $K_n$ with $n = R_r(H)$ is $r$-Ramsey for $H$, but it might not be minimal. Still, we can look at a subgraph of $K_n$ which is minimal to conclude that $s_r(H) \leq \delta(K_n) = n - 1 = R_r(H) - 1$. We can see that this gives us the bound $s_2(k) \leq 2^{2k} - 1$, using the upper bound on $R(k)$ I mentioned above. In fact, we can’t hope to get any subexponential upper bound on $s_2(k)$ using this easy argument as we also saw that $R(k) \geq 2^{k/2}$. Quite surprisingly, we do know $s_2(k)$ exactly (which is something that rarely happens in Ramsey theory), and it is far far away from an exponential function!

In 1976, Burr, Erdős and Lovász proved that $s_2(k) = (k - 1)^2$. Thus, they showed that there exists a graph in $\mathcal{M}_r(K_k)$ with minimum degree equal to $(k - 1)^2$, and there can’t be any graph in this set with a smaller minimum degree. Determining $s_r(k)$ for $r > 2$ is still widely open. It’s an instructive exercise to try to come up with a graph in $\mathcal{M}_2(K_3)$ with minimum degree $4$. The proof of the upper bound by Burr, Erdős and Lovász uses the existence of certain (very large) graphs, known as signal senders, that are (i) not $2$-Ramsey for $K_k$ and (ii) in any such monochromatic $H$-free colouring of these graphs two specific edges of the graph receive a specific colour pattern. These signal senders are then used to construct $2$-Ramsey minimal graphs with the required minimum degree. The same idea has been very fruitful in determining $s_r(H)$ for other graphs $H$, and some related problems (see this, this, this and this).

Signal senders are also an important ingredient in the work of Fox, Grinshpun, Liebenau, Person and Szabó,  where they reduce the problem of determining $s_r(k)$ to another extremal problem on graph packings. This reduction helped them determine $s_r(k)$ up-to polylogarithmic factors assuming $k \geq 3$ is a constant and $r \rightarrow \infty$. The constants $C_k$ in this bound were terribly large, and in particular not polynomial in $k$. Therefore, they proved the general upper bound of $s_r(k) \leq 8 (k - 1)^6 r^3.$ Pushing their idea further, and using a nice finite geometric and group theoretic ingredient that I haven’t seen used anywhere in extremal combinatorics so far,  we have managed to improve this general upper bound.

Theorem 2. (Bamberg, Bishnoi, Lesgourgues) There exists an absolute constant $C$ such that for all $r \geq 2$ and $k \geq 3$, we have $s_r(k) \leq C (k - 1)^5 r^{5/2}$.

I will discuss the details of this result in the next post, and explain the finite geometric aspect of it which I find super interesting. I am really hopeful that the ideas involved will be useful in obtaining new results in other Ramsey problems. 