On 19.10.2006 at 12:20 in S5, there is the following noon lecture:
Constrained random graph processes
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.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010