The Lovász Number of Random Graphs

DOI10.1017/S0963548305006826MaRDI QIDQ5696358zbMATH OpenFDO

Authors Amin Coja-Oghlan

Publication date 18 October 2005

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0306266

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: 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.

Recommendations

• The Lovász number of random graphs
• scientific article; zbMATH DE number 1670810
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Approximating the independence number and the chromatic number in expected polynomial time
• The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs

Cited in

(16)

• On the Lovász \(\vartheta\)-number of almost regular graphs with application to Erdős-Rényi graphs
• Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
• Approximating the independence number and the chromatic number in expected polynomial time
• The theta number of simplicial complexes
• Limit distributions of the number of loops in a random configuration graph
• scientific article; zbMATH DE number 1507223 (Why is no real title available?)
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• The Lovász theta function for random regular graphs and community detection in the hard regime
• On minrank and the Lovász theta-function
• The Lovász theta function for random regular graphs and community detection in the hard regime
• The Lovász number of random graphs
• The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs
• A Sum of Squares Characterization of Perfect Graphs
• On linear and semidefinite programming relaxations for hypergraph matching
• An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
• The Grothendieck constant of random and pseudo-random graphs

This page was built for publication: The Lovász Number of Random Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5696358)