The Ramsey number <i>R</i>(3, <i>t</i>) has order of magnitude <i>t</i>²/log <i>t</i> 论文

摘要

Abstract The Ramsey number R(s, t) for positive integers s and t is the minimum integer n for which every red‐blue coloring of the edges of a complete n ‐vertex graph induces either a red complete graph of order s or a blue complete graph of order t . This paper proves that R (3, t ) is bounded below by (1 – o (1)) t / 2 /log t times a positive constant. Together with the known upper bound of (1 + o (1)) t 2 /log t , it follows that R (3, t ) has asymptotic order of magnitude t 2 /log t . © 1995 John Wiley &amp; Sons, Inc.