Isolated clique appearance in a uniform random graph process
ID: isolated-clique-appearance-in-a-uniform-random-graph-process
In a uniform random graph process, realize edge arrivals by independent continuous uniform times. For a fixed set of vertices to form an isolated clique at some time, all internal edges must arrive before the first of the outgoing edges. Their relative arrival ordering is uniform, so the exact probability isA union bound over the vertex sets therefore bounds the probability that such an isolated clique ever appears by . For fixed this is , since . This argument controls all process times at once, including the short interval during which an isolated component could exist, without discretizing time.
New to topics? Read the docs here!