Dynamic concentration of the triangle-free process

2013-02-24T00:00:00Z (GMT) by Tom Bohman Peter Keevash
<p>The triangle-free process begins with an empty graph on <em>n</em> 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 Ramsey numbers: we show <em>R</em>(3,<em>t</em>) > (1/4 − <em>o</em>(1))<em>t</em> 2/ log <em>t</em>, which is within a 4 + <em>o</em>(1) factor of the best known upper bound. 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 maximal average density at most 2.</p>