Ramsey’s Theorem is one of the oldest theorems in graph theory. In its simplest form, it asserts that for every , there exists such that any coloring of the edges of the complete graph with two colors contains a monochromatic copy of . The smallest such is referred to as the Ramsey number . Despite a very long history, the exact value of is known only for and determining for 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 copies of the same graph , which is a subject of this paper.
In 1975, Burr, Erdős and Spencer showed that the Ramsey number of copies of the same graph is equal to when . The value of is equal to twice the number of vertices minus the independence number of , and a way of computing the value of was presented by Burr in the 1980s. For example, it holds that and . The bound on the threshold given by Burr is triple exponential in the number of vertices of . The main result of the manuscript yields a single exponential bound on , which is asymptotically best possible (as and so the threshold grows exponentially in ).