31 January 2012

14:30

Lutz Warnke

Abstract

<p>In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. Although the evolution of such `local' modifications of the Erdös-Rényi random graph processes has received considerable attention during the last decade, so far only rather `simple' rules are well-understood. Indeed, the main focus has been on bounded size rules (where all component sizes larger than some constant B are treated the same way), and for more complex rules hardly any rigorous results are known. In this talk we will discuss a new approach that applies to many involved Achlioptas processes: it allows us to prove that certain key statistics are tightly concentrated during the early evolution of e.g. the sum and product rule.</p>
<p>Joint work with Oliver Riordan.</p>