Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-09T02:41:47.113Z 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: coja@informatik.hu-berlin.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
© 2005 Cambridge University Press