Avoiding small subgraphs in Achlioptas processes

Details Avoiding small subgraphs in Achlioptas processes Avoiding small subgraphs in Achlioptas processes

2007-08-03

arxiv.org/abs/0708.0443v2

Mathematics

Combinatorics

43 pages; reorganized and shortened

Scientific paper

For a fixed integer r, consider the following random process. At each round, one is presented with r random edges from the edge set of the complete graph on n vertices, and is asked to choose one of them. The selected edges are collected into a graph, which thus grows at the rate of one edge per round. This is a natural generalization of what is known in the literature as an Achlioptas process (the original version has r=2), which has been studied by many researchers, mainly in the context of delaying or accelerating the appearance of the giant component. In this paper, we investigate the small subgraph problem for Achlioptas processes. That is, given a fixed graph H, we study whether there is an online algorithm that substantially delays or accelerates a typical appearance of H, compared to its threshold of appearance in the random graph G(n, M). It is easy to see that one cannot accelerate the appearance of any fixed graph by more than the constant factor r, so we concentrate on the task of avoiding H. We determine thresholds for the avoidance of all cycles C_t, cliques K_t, and complete bipartite graphs K_{t,t}, in every Achlioptas process with parameter r >= 2.

Affiliated with

Also associated with

No associations

Rating

Avoiding small subgraphs in Achlioptas processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Avoiding small subgraphs in Achlioptas processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Avoiding small subgraphs in Achlioptas processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-601746