Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 19.10.2006 at 12:20 in S5, there is the following noon lecture:

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.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010