The triangle-free process

By Tom Bohman. 2008

169 citations recorded by the source corpus.

Consider the following stochastic graph process. We begin with G0, the empty graph on n vertices, and form Gi by adding a randomly chosen edge ei to Gi−1 where ei is chosen uniformly at random from the collection of pairs of vertices that neither appear as edges in Gi−1 nor form triangles when added as edges to Gi−1. Let the random variable M be the number of edges in the maximal triangle free graph generated by this process. We prove that asymptotically almost surely M=Θ(n3/2logn). This resolves a conjecture of Spencer. Furthermore, the independence number of GM is asymptotically almost surely Θ(nlogn), which implies that the Ramsey number R(3,t) is bounded below by a constant times t2/logt (a fact that was previously established by Jeong Han Kim). The methods introduced here extend to the K4-free process, thereby establishing the bound R(4,t)=Ω(t5/2/log2t).

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/8257effcaac41e1193b22c10e7f0299d7781dfb2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

The early evolution of the H-free process (2009, methodology): “7 we formulate our framework for showing that the process follows the differential equations, which is based to some extent on that given by Wormald [37], but also incorporates martingale estimates from [7].”
An exponential improvement for diagonal Ramsey (2023, unknown): “Let us note also here that the best lower bound for R(k, `), proved using Erdős’ random colouring, is roughly the square root of the upper bound, so there is unfortunately still a large gap between the known bounds, except in the case ` = 3 (see [1, 3, 4, 12,15,19]).”
Random triangle removal (2012, background): “n3/2+o(1), and the correct order of n3/2 √ log n, along with its ramifications on the Ramsey number R(3, t), was recovered in [3] (see also [5] for generalizations).”
Coloring plane graphs with independent crossings (2010, background): “Recently, Bohman [1] gave an alternative proof of Kim’s result by analyzing the so-called triangle-free process, as proposed by Erdős, Suen and Winkler [3], which is a natural way of generating a triangle-free graph.”
Hypergraph Ramsey numbers (2008, background): “ (see [1], [20], [27]) that there are constants c1,...,c4 such that c1 n2 logn ≤ r(3,n) ≤ c2 n2 logn , and for ﬁxed s > 3, c3 n logn (s+1)/2 ≤ r(s,n) ≤ c4 ns−1 logs−2 n , (1) (For s = 4, Bohman [3] recently improved the lower bound by a factor of log1/2 n.) All logarithms in this paper are base ”
The triangle-free process and R(3,k) (2013, background): “As noted above, it follows from the ErdősSzekeres bound (1) that R(3, k) = O(k(2)) and, in a visionary paper from 1961, Erdős [27] proved a lower bound of order k(2)/(log k)(2) by applying a deterministic algorithm to the random graph G(n, p).”