Randomized graph products, chromatic numbers, and the Lovasz theta-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 such that theta(G) > alpha(G)n/2(c root log n), where n denotes the number of vertices in a graph. This disproves a known conjecture regarding the theta function. As part of our proof, we analyse the behavior of the chromatic number in graphs under a randomized version of graph products. This analysis extends earlier work of Linial and Vazirani, and of Berman and Schnitger, and may be of independent interest.