Hamiltonicity thresholds in Achlioptas processes
Hamiltonicity thresholds in Achlioptas processes
In this article, we analyze the appearance of a Hamilton cycle in the following random process. The process starts with an empty graph on nlabeled vertices. At each round we are presented with K = K(n) edges, chosen uniformly at random from the missing ones, and are asked to add …