Tight Ramsey bounds for multiple copies of a graph
- Mathematics, Princeton University and Institute for Advanced Study
- ORCID iD: 0000-0002-1055-3309
- More about Matija Bucić
- Mathematics, ETH Zurich
- More about Benny Sudakov
Editorial introduction
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 KN with two colors contains a monochromatic copy of Kk. 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∈{1,2,3,4} and determining R(k) for k≥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 aHn+bH when n≥nH. The value of aH is equal to twice the number of vertices minus the independence number of H, and a way of computing the value of bH was presented by Burr in the 1980s. For example, it holds that aKk=2k−1 and bKk=R(k−1)−2. The bound on the threshold nH 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 nH, which is asymptotically best possible (as nKk≥(R(k)−R(k−1)+2)/(2k−1) and so the threshold nKk grows exponentially in k).