Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-17T18:22:06.039Z Has data issue: false hasContentIssue false

The Lovász Number of Random Graphs

Published online by Cambridge University Press:  21 July 2005

AMIN COJA-OGHLAN
Affiliation:
Humboldt-Universität zu Berlin, Institut für Informatik, Unter den Linden 6, 10099 Berlin, Germany (e-mail: [email protected])

Abstract

We study the Lovász number $\vartheta$ along with two related SDP relaxations $\vartheta_{1/2}$, $\vartheta_2$ of the independence number and the corresponding relaxations $\bar\vartheta$, $\bar\vartheta_{1/2}$, $\bar\vartheta_2$ of the chromatic number on random graphs $G_{n,p}$. We prove that $\vartheta,\vartheta_{1/2},\vartheta_2(G_{n,p})$ are concentrated about their means, and that $\bar\vartheta,\bar\vartheta_{1/2},\bar\vartheta_2(G_{n,p})$ in the case $p<n^{-1/2-\varepsilon}$ are concentrated in intervals of constant length. Moreover, extending a result of Juhász [28], we estimate the probable value of $\vartheta,\vartheta_{1/2},\vartheta_2(G_{n,p})$ for edge probabilities $c_0/n\leq p\leq 1-c_0/n$, where $c_0>0$ is a constant. As an application, we give improved algorithms for approximating the independence number of $G_{n,p}$ and for deciding $k$-colourability in polynomial expected time.

Type
Paper
Copyright
© 2005 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)