No dense subgraphs appear in the triangle-free graph process (Q640423): Difference between revisions

Summary: 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.