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.

 

 

 

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Extremal Combinatorics, Finite Geometry, Incidence Geometry, Ramsey Theory and tagged , , , , , , . Bookmark the permalink.

2 Responses to Minimal Ramsey problems

  1. Pingback: Generalized polygons in extremal combinatorics | Anurag's Math Blog

  2. Pingback: Heisenberg groups, irreducible cubics and minimal Ramsey | Anurag's Math Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s