Dynamic concentration of the triangle‐free process. Issue 2 (17th November 2020)

• Record Type: Journal Article
• Authors: Bohman, Tom; Keevash, Peter
• Is Part Of: Random structures & algorithms. Volume 58:Issue 2(2021)
• Page Start: 221
• Page End: 293
• Publication Date: 2020-11-17
• Subjects: dynamic concentration -- Ramsey numbers -- triangle‐free; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20973
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : The triangle‐free process begins with an empty graph on n vertices and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. We determine the asymptotic number of edges in the maximal triangle‐free graph at which the triangle‐free process terminates. We also bound the independence number of this graph, which gives an improved lower bound on the Ramsey numbers R (3, t ): we show R ( 3, t ) > ( 1 / 4 − o ( 1 ) ) t 2 / log t, which is within a 4 + o (1) factor of the best known upper bound. Our improvement on previous analyses of this process exploits the self‐correcting nature of key statistics of the process. Furthermore, we determine which bounded size subgraphs are likely to appear in the maximal triangle‐free graph produced by the triangle‐free process: they are precisely those triangle‐free graphs with density at most 2.