EXCEPTIONAL TIMES OF THE CRITICAL DYNAMICAL ERDOS-RENYI GRAPH

• 成果类型: Article
• 署名作者: Roberts, Matthew, I; Sengul, Bati
• 署名单位: University of Bath; Bank of America Corporation
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/17-AAP1357
• 发表日期: 2018
• 页码: 2275-2308
• 关键词: noise sensitivity; percolation

摘要

In this paper, we introduce a network model which evolves in time, and study its largest connected component. We consider a process of graphs (G(t) : t is an element of [0, 1]), where initially we start with a critical Erdos-Renyi graph ER(n, 1/n), and then evolve forward in time by resampling each edge independently at rate 1. We show that the size of the largest connected component that appears during the time interval [0, 1] is of order n(2/3) log(1/3)n with high probability. This is in contrast to the largest component in the static critical Erdos-Renyi graph, which is of order n(2/3).