The Triangle-Free Process and the Ramsey Number R(3,k)
Apr 2020 · American Mathematical Soc.
Ebook
125
Pages
About this ebook
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 Kn 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 Gn,△. 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)=Θ(k2/logk).
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.
About the author
Instituto Nacional de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, Brasil
Instituto Nacional de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, Brasil
Instituto Nacional de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, Brasil
Rate this ebook
Tell us what you think.
Reading information
Smartphones and tablets
Install the Google Play Books app for Android and iPad/iPhone. It syncs automatically with your account and allows you to read online or offline wherever you are.
Laptops and computers
You can listen to audiobooks purchased on Google Play using your computer's web browser.
eReaders and other devices
To read on e-ink devices like Kobo eReaders, you'll need to download a file and transfer it to your device. Follow the detailed Help Center instructions to transfer the files to supported eReaders.
