Department of
Applied
Mathematics

Constrained random graph processes

Dirk Schlatter

Abstract

A constrained random graph process is a generalisation of the classical random graph process introduced by Erdős and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains within a decreasing graph property P. We mainly consider the case when P is characterized by a set of forbidden 2-connected minors and show that, with high probability, a constant fraction of all edges have to be tested before the number of edges in the graph reaches (1+\epsilon)n. At this point, the graph contains w.h.p. a linear number of copies of a fixed graph in P.