CONNECTIVITY THRESHOLDS FOR BOUNDED SIZE RULES

• 成果类型: Article
• 署名作者: Einarsson, Hafsteinn; Lengler, Johannes; Mousset, Frank; Panagiotou, Konstantinos; Steger, Angelika
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Munich
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/16-AAP1174
• 发表日期: 2016
• 页码: 3206-3250
• 关键词: achlioptas processes; phase-transitions; small subgraphs

摘要

In an Achlioptas process, starting with a graph that has n vertices and no edge, in each round d >= 1 vertex pairs are chosen uniformly at random, and using some rule exactly one of them is selected and added to the evolving graph. We investigate the impact of the rule's choice on one of the most basic properties of a graph: connectivity. In our main result we focus on 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 fine analysis that exposes the limiting distribution and the expectation 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. 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.