Connectivity Thresholds for Bounded Size Rules

Tuesday, September 9, 2014 - 9:00am - 9:50am
Keller 3-180
Angelika Steger (ETH Zürich)
In an Achlioptas processes, starting with a graph that has n vertices
and no edge, in each round d edges are drawn uniformly
at random, and using some rule exactly one of them is chosen and
added to the evolving graph. For the class of Achlioptas processes
we investigate how much impact the rule has on one of the most basic
properties of a graph: connectivity. Our main results are twofold.
First, we study the prominent class of bounded size rules, which select
the edge to add according to the component sizes of its vertices,
treating all sizes larger than some constant equally. For such rules
we provide a ne analysis that exposes the limiting distribution of
the number of rounds until the graph gets connected, and we give a
detailed picture of the dynamics of the formation of the single component
from smaller components. Second, our results allow us to study
the connectivity transition of all Achlioptas processes, in the sense
that we identify a process that accelerates it as much as possible.

Joint work with Hafsteinn Einarsson, Johannes Lengler, Frank Mousset, and
Konstantinos Panagiotou