Tight Ramsey bounds for multiple copies of a graph

Ramsey’s Theorem is one of the oldest theorems in graph theory. In its simplest form, it asserts that for every $k$, there exists $N$ such that any coloring of the edges of the complete graph $K_N$ with two colors contains a monochromatic copy of $K_k$. The smallest such $N$ is referred to as the Ramsey number $R(k)$. Despite a very long history, the exact value of $R(k)$ is known only for $k\in\{1,2,3,4\}$ and determining $R(k)$ for $k\ge 5$ is considered one of the most challenging and intriguing problems in graph theory. Similarly, in settings that extend Ramsey’s Theorem, the values of Ramsey numbers are known only in a very limited number of cases. One notable exception is the Ramsey number of $n$ copies of the same graph $H$, which is a subject of this paper.

In 1975, Burr, Erdős and Spencer showed that the Ramsey number of $n$ copies of the same graph $H$ is equal to $a_H n+b_H$ when $n\ge n_H$. The value of $a_H$ is equal to twice the number of vertices minus the independence number of $H$, and a way of computing the value of $b_H$ was presented by Burr in the 1980s. For example, it holds that $a_{K_k}=2k-1$ and $b_{K_k}=R(k-1)-2$. The bound on the threshold $n_H$ given by Burr is triple exponential in the number of vertices of $H$. The main result of the manuscript yields a single exponential bound on $n_H$, which is asymptotically best possible (as $n_{K_k}\ge (R(k)-R(k-1)+2)/(2k-1)$ and so the threshold $n_{K_k}$ grows exponentially in $k$).

Talk on manuscript results