A fixed-choice Achlioptas process cannot have its largest component of a graph jump from to a fixed positive fraction of within steps, with high probability. The proof combines forced merging of large components and persistence of unsampled graph components. An assumed jump forces positive vertex mass in each band slightly before the jump: insufficient smaller components can feed the final large component, while enough components above would merge too early. Persistence carries a fixed positive amount of each band to a common time. Taking sufficiently many disjoint bands with then counts more than vertices. The number of offered candidates is fixed throughout this argument. Riordan and Warnke establish this obstruction and broader continuity results in their original research paper.

Articles by others on the same topic (0)

There are currently no matching articles.