ECCC-Report TR03-073https://eccc.weizmann.ac.il/report/2003/073Comments and Revisions published for TR03-073en-usThu, 09 Oct 2003 17:39:01 +0200
Paper TR03-073
| The Lovasz number of random graph |
Amin Coja-Oghlan
https://eccc.weizmann.ac.il/report/2003/073We study the Lovasz number theta along with two further SDP relaxations $\thetI$, $\thetII$
of the independence number and the corresponding relaxations of the
chromatic number on random graphs G(n,p). We prove that \theta is
concentrated about its mean, and that the relaxations of the chromatic
number in the case p<n^-1/2 are concentrated in intervals of constant
length. Moreover, we compute the probable value of theta(G(n,p)).
As an application, we give an improved algorithm for approximating the
independence number of in polynomial expected time. We also improve on
the analysis of an algorithm of Krivelevich for deciding whether G(n,p)
is k-colorable.
Thu, 09 Oct 2003 17:39:01 +0200https://eccc.weizmann.ac.il/report/2003/073