Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function (Q1375058): Difference between revisions

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.