![Für diesen Artikel ist leider kein Bild verfügbar.](/img/platzhalter480px.png)
The Triangle-Free Process and the Ramsey Number $R(3,k)$
Seiten
2020
American Mathematical Society (Verlag)
978-1-4704-4071-8 (ISBN)
American Mathematical Society (Verlag)
978-1-4704-4071-8 (ISBN)
The areas of Ramsey theory and random graphs have been closely linked ever since Erdos'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.
Gonzalo Fiz Pontiveros, Instituto Nacional de Matematica Pura e Aplicada (IMPA), Rio de Janeiro, Brasil Simon Griffiths, Instituto Nacional de Matematica Pura e Aplicada (IMPA), Rio de Janeiro, Brasil Robert Morris, Instituto Nacional de Matematica Pura e Aplicada (IMPA), Rio de Janeiro, Brasil
Introduction
An overview of the proof
Martingale bounds: the line of peril and the line of death
Tracking everything else
Tracking $Y_e$, and mixing in the $Y$-graph
Whirlpools and Lyapunov functions
Independent sets and maximum degrees in $G_n,/triangle $
Bibliography.
Erscheinungsdatum | 03.03.2020 |
---|---|
Reihe/Serie | Memoirs of the American Mathematical Society |
Verlagsort | Providence |
Sprache | englisch |
Maße | 178 x 254 mm |
Gewicht | 254 g |
Themenwelt | Mathematik / Informatik ► Mathematik ► Graphentheorie |
ISBN-10 | 1-4704-4071-7 / 1470440717 |
ISBN-13 | 978-1-4704-4071-8 / 9781470440718 |
Zustand | Neuware |
Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
Grundlagen, Methoden, Anwendungen
Buch | Hardcover (2024)
Carl Hanser (Verlag)
34,99 €
Numbers and Counting, Groups, Graphs, Orders and Lattices
Buch | Softcover (2023)
De Gruyter (Verlag)
59,95 €