No Dense Subgraphs Appear in the Triangle-free Graph Process
Stefanie Gerke, Tamás Makai · The Electronic Journal of Combinatorics · 2011
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2011
Abstract
Consider the triangle-free graph process, which starts from the empty graph on $n$ vertices and in every step an edge is added that is chosen uniformly at random from all non-edges that do not form a triangle with the existing edges. We will show that there exists a constant $c$ such that asymptotically almost surely no copy of any fixed finite triangle-free graph on $k$ vertices with at least $ck$ edges appears in the triangle-free graph process.
Open the resolved locator · 10.37236/655
Metadata licence: OpenAlex metadata (CC0)