The classical Ramsey numbers r(s, t) denote the minimum n such that every red-blue coloring of the edges of the complete graph \(K_n\) contains either a red clique of order s or a blue clique of order t. These quantities are the centerpiece of graph Ramsey Theory, and have been studied for almost a century. The Erdős-Szekeres Theorem (1935) shows that for each \(s \ge 2\) , \(r(s,t) = O(t^{s - 1})\) as \(t \rightarrow \infty \) . The celebrated work of Kim (1995) together with the work of Ajtai et al. (1980) and Shearer (1983) shows \(r(3,t) = \Theta (t^2/\log t)\) as \(t \rightarrow \infty \) . We introduce a new approach using pseudorandom graphs, which shows \(r(4,t) = \Omega (t^3/(\log t)^4)\) as \(t \rightarrow \infty \) , answering an old conjecture of Erdős, and we illustrate how to apply this approach to many other Ramsey and related combinatorial problems.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Recent Progress in Ramsey Theory

  • Jacques Verstraete

摘要

The classical Ramsey numbers r(s, t) denote the minimum n such that every red-blue coloring of the edges of the complete graph \(K_n\) contains either a red clique of order s or a blue clique of order t. These quantities are the centerpiece of graph Ramsey Theory, and have been studied for almost a century. The Erdős-Szekeres Theorem (1935) shows that for each \(s \ge 2\) , \(r(s,t) = O(t^{s - 1})\) as \(t \rightarrow \infty \) . The celebrated work of Kim (1995) together with the work of Ajtai et al. (1980) and Shearer (1983) shows \(r(3,t) = \Theta (t^2/\log t)\) as \(t \rightarrow \infty \) . We introduce a new approach using pseudorandom graphs, which shows \(r(4,t) = \Omega (t^3/(\log t)^4)\) as \(t \rightarrow \infty \) , answering an old conjecture of Erdős, and we illustrate how to apply this approach to many other Ramsey and related combinatorial problems.