The Lovasz number of random graphs

Details The Lovasz number of random graphs The Lovasz number of random graphs

2003-06-18

arxiv.org/abs/math/0306266v1

Mathematics

Combinatorics

Scientific paper

We study the Lovasz number theta along with two further SDP relaxations theta1, theta1/2 of the independence number and the corresponding relaxations of the chromatic number on random graphs G(n,p). We prove that these relaxations are concentrated about their means Moreover, extending a result of Juhasz, we compute the asymptotic value of the relaxations for essentially the entire range of edge probabilities p. As an application, we give an improved algorithm for approximating the independence number in polynomial expected time, thereby extending a result of Krivelevich and Vu. We also improve on the analysis of an algorithm of Krivelevich for deciding whether G(n,p) is k-colorable.

Affiliated with

Also associated with

No associations

Rating

The Lovasz number of random graphs 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 Lovasz number of random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Lovasz number of random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-51141