Premium
The Ramsey number R (3, t ) has order of magnitude t 2 /log t
Author(s) -
Kim Jeong Han
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240070302
Subject(s) - combinatorics , mathematics , graph , ramsey's theorem , vertex (graph theory) , bounded function , order (exchange) , integer (computer science) , upper and lower bounds , discrete mathematics , computer science , mathematical analysis , finance , economics , programming language
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 & Sons, Inc.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom