Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
type: Item
instance of: scholarly article
title: Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
zbMATH Open document ID: 0880.05032
DOI: 10.1007/BF01196133
published in: Combinatorica
publication date: 1998-01-05T00:00:00Z
review text: Let \(G\) be a graph on \(n\) vertices. Denote by \(\alpha (G)\) the size of the largest independent set in \(G\), by \(\theta (G)\) the Lovász \(\theta\)-function on \(G\), and by \(\overline\chi (G)\) the chromatic number of the complement of \(G\). The main result of this paper says that for some constant \(c>0\) there exist an infinite family of graphs for which \(\theta (G)<2^{\sqrt{\log n}} \)and \(\overline\chi (G)>n/2^{c\sqrt{\log n}}\). Likewise, for some constant \(c>0\) there exist an infinite family of graphs for which \(\alpha (G)<2^{\sqrt{\log n}}\) and \(\theta (G)>n/2^{c\sqrt{\log n}}\). This disproves two conjectures showed to be equivalent by Szegedy and a conjecture attributed to Lovász. The (randomized) construction of graphs satisfying the above requirements is based on the ``randomized graph products'' technique of Berman and Schnitger. Several classical nonapproximability results are shown to be nice consequences of the construction given in this paper. An open question leading to the construction of Ramsey graphs is posed.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 1099682
zbMATH Keywords: graph
zbMATH Keywords: chromatic number
zbMATH Keywords: largest independent set
zbMATH Keywords: graph product
zbMATH Keywords: Lovász \(\theta\)-function
zbMATH Keywords: NP-hard
MaRDI profile type: Publication
cites work: Approximating the independence number via the \(\vartheta\)-function
cites work: Q4230322
cites work: Q4230321
cites work: Q4252727
cites work: On the complexity of approximating the independent set problem
cites work: New approximation algorithms for graph coloring
cites work: Interactive proofs and the hardness of approximating cliques
cites work: Intersection theorems with geometric consequences
cites work: Q4252726
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Approximate graph coloring by semidefinite programming
cites work: The sandwich theorem
cites work: On the ratio of optimal integral and fractional covers
cites work: On the Shannon capacity of a graph
cites work: On the hardness of approximating minimization problems
cites work: On cliques in graphs
cites work: Improving the performance guarantee for approximate graph coloring
author: Uriel Feige
description: scientific article; zbMATH DE number 1099682