Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 08, 2013, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Johannes Lengler
Achlioptas processes are often considered to understand the power of choices. In such a process, we start with an empty graph. In each round, Decision Maker is presented k edges and may choose one of them to be inserted into the graph. If his policy is only based on the component sizes of the endpoints, then we call it a size rule. If moreover Decision Maker treats all component sizes > L equally, then we call it a bounded size rule.
In this talk we will explore bounded size rules and their effects on the time T when the graph becomes connected. We will see that some very precise statements on this time can be obtained. In particular, we show how differential equations can be used to derive the probability distribution for T for any bounded size rule.
The results are shared work with Hafsteinn Einarsson, Frank Mousset, Konstantinos Panagiotou, and Angelika Steger. They were obtained in the traditional annual Buchboden retreat which transformed plenty of nice food into plenty of nice theorems.
Automatic MiSe System Software Version 1.4803M | admin login