Name
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))t2/logt, 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1002/rsa.20973 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | DocType | Volume |
dynamic concentration, Ramsey numbers, triangle‐, free | Journal | 58 |
Issue | ISSN | Citations |
2 | 1042-9832 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tom Bohman | 1 | 250 | 33.01 |
| Peter Keevash | 2 | 0 | 0.34 |