The triangle-free process and the Ramsey number R(3, k) / Gonzalo Fiz Pontiveros, Simon Griffiths, Robert Morris.

Format:

Book

Author/Creator:

Pontiveros, Gonzalo Fiz, author.

Griffiths, Simon, author.

Morris, Robert, author.

Series:

Memoirs of the American Mathematical Society ; no. 1274.

Memoirs of the American Mathematical Society, 0065-9266 ; volume 263, number 1274

Language:

English

Subjects (All):

Combinatorial analysis.

Ramsey theory.

Ramsey numbers.

Physical Description:

v, 125 pages ; 26 cm.

Place of Publication:

Providence, RI : American Mathematical Society, 2020.

Summary:

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 [subscript 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[subscript n, subscript 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] (k2/log k). 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.

Contents:

Chapter 1. Introduction

Chapter 2. An overview of the proof

Chapter 3. Martingale bounds: The line of peril and the line of death

Chapter 4. Tracking everything else

Chapter 5. Tracking Y [subscript e], and mixing in the Y-graph

Chapter 6. Whirlpools and Lyapunov functions

Chapter 7. Independent sets and maximum degrees in G[subscript n, subscript triangle].

Notes:

Includes bibliographical references (pages 123-125).

ISBN:

9781470440718

1470440717

OCLC:

1132237011