Upper bounds on the theta function of random graphs
Abstract:
The theta function of Lovasz is a graph parameter that can be computed up to arbitrary precision in polynomial time. It plays a key role in algorithms that approximate graph parameters such as maximum independent set, maximum clique and chromatic number, or even compute them exactly in some models of random and semi-random graphs. For Erdos-Renyi random $G_{n,1/2}$ graphs, the expected value $\vartheta(G)$ of the theta function of $G\sim G_{n,1/2}$ is known to be at most $2\sqrt{n}$ and at least $\sqrt{n}$. These bounds have not been improved in over 40 years.
In this talk, we introduce a new approach to upper bounding the value of the theta function of random graphs and present several heuristic arguments supporting it, which strongly suggest that the expected value of $\vartheta(G)$ for $G\sim G_{n,1/2}$ is below $1.55\sqrt{n}$. The approach is based on methods from spectral analysis, random matrix theory and free probability. We fall short of rigorously proving such an upper bound, because our analysis makes use of unproven assumptions.