Konstantinos Panagiotou (University of Munich)

Event Date: 

Wednesday, September 27, 2017 -
3:30pm to 5:00pm

Event Date Details: 

Refreshments served at 3:15pm

Event Location: 

  • TBD
  • Department Seminar Series

Abstract: In an Achlioptas process, starting with a graph that has n vertices and no edge, in each round d >= 1 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. The main result includes a fine study of 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 detailed 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.