go-v.orgdoi

No Dense Subgraphs Appear in the Triangle-free Graph Process

Stefanie Gerke, Tamás Makai · The Electronic Journal of Combinatorics · 2011

  • DOI 10.37236/655
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 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)