RANDOMIZED GRAPH PRODUCTS, CHROMATIC-NUMBERS, AND THE LOVASZ NU-FUNCTION

For a graph G, let alpha(G) denote the size of the largest independent set in G, and let theta(G) denote the Lovasz theta-function on G. We prove that for some c > 0, there exists an infinite family of graphs s uch that theta(G) > alpha(G)n/2(c root log n), where n denotes the num ber of vertices in a graph. This disproves a known conjecture regardin g the theta function. As part of our proof, we analyse the behavior of the chromatic number in graphs under a randomized version of graph pr oducts. This analysis extends earlier work of Linial and Vazirani, and of Berman and Schnitger, and may be of independent interest.