Triangle-Free Process and the Ramsey Number $R(3,k)$ (eBook)

Gonzalo Fiz Pontiveros (Autor)

eBook Download: PDF

2020
125 Seiten
American Mathematical Society (Verlag)
978-1-4704-5656-6 (ISBN)

Infos

The areas of Ramsey theory and random graphs have been closely linked ever since Erdos's famous proof in 1947 that the "e;diagonal"e; 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 "e;off-diagonal"e; 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.

Produkt-Details

• Erscheint lt. Verlag: 4.3.2020
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• ISBN-10: 1-4704-5656-7 / 1470456567
• ISBN-13: 978-1-4704-5656-6 / 9781470456566