Uniform random graph process

ID: uniform-random-graph-process

Start with the empty graph and reveal the edges of the complete graph in a uniformly random order. After steps its edge set is a uniform -element subset. Independent uniform edge labels couple this process with all binomial random graphs: , where has a binomial distribution with parameters . For a monotone graph property, concentration of transfers a threshold estimate between edge probability and edge count.

New to topics? Read the docs here!