Cargando…

The triangle-free process and the Ramsey number

The areas of Ramsey theory and random graphs have been closely linked ever since Erdős's famous proof in 1947 that the "diagonal" Ramsey numbers R(k) grow exponentially in k. In the early 1990s, the triangle-free process was introduced as a model which might potentially provide good...

Descripción completa

Detalles Bibliográficos
Autores principales: Pontiveros, Gonzalo Fiz, Griffiths, Simon, Morris, Robert
Lenguaje:eng
Publicado: American Mathematical Society 1920
Materias:
XX
Acceso en línea:http://cds.cern.ch/record/2763645
Descripción
Sumario:The areas of Ramsey theory and random graphs have been closely linked ever since Erdős's famous proof in 1947 that the "diagonal" Ramsey numbers R(k) grow exponentially in k. In the early 1990s, the triangle-free process was introduced as a model which might potentially provide good lower bounds for the "off-diagonal" Ramsey numbers R(3,k). In this model, edges of K_n are introduced one-by-one at random and added to the graph if they do not create a triangle; the resulting final (random) graph is denoted G_n,\triangle . In 2009, Bohman succeeded in following this process for a positive fraction of its duration, and thus obtained a second proof of Kim's celebrated result that R(3,k) = \Theta \big ( k^2 / \log k \big ). In this paper the authors improve the results of both Bohman and Kim and follow the triangle-free process all the way to its asymptotic end.