The order of the largest complete minor in a random graph

Details The order of the largest complete minor in a random graph The order of the largest complete minor in a random graph

2007-05-02

arxiv.org/abs/0705.0325v1

Mathematics

Combinatorics

14 pages

Scientific paper

Let ccl(G) denote the order of the largest complete minor in a graph G (also called the contraction clique number) and let G(n,p) denote a random graph on n vertices with edge probability p. Bollobas, Catlin and Erdos asymptotically determined ccl(G (n,p)) when p is a constant. Luczak, Pittel and Wierman gave bounds on ccl(G(n,p)) when p is very close to 1/n, i.e. inside the phase transition. Extending the results of Bollobas, Catlin and Erdos, we determine ccl(G(n,p)) quite tightly, for p>C/n where C is a large constant. If p=C/n, for an arbitrary constant C>1, then we show that asymptotically almost surely ccl(G (n,p)) is of order square-root of n. This answers a question of Krivelevich and Sudakov.

Affiliated with

Also associated with

No associations

Rating

The order of the largest complete minor in a random graph 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 The order of the largest complete minor in a random graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The order of the largest complete minor in a random graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-675116