We prove that in sparse ErdH{o}s-R{e}nyi graphs of average degree $d$, the vector chromatic number (the relaxation of chromatic number coming from the Lov`{a}sz theta function) is typically $tfrac{1}{2}sqrt{d} + o_d(1)$. This fits with a long-standing conjecture that various refutation and hypothesis-testing problems concerning $k$-colorings of sparse ErdH{o}s-R{e}nyi graphs become computationally intractable below the `Kesten-Stigum threshold $d_{KS,k} = (k-1)^2$. Along the way, we use the celebrated Ihara-Bass identity and a carefully constructed non-backtracking random walk to prove two deterministic results of independent interest: a lower bound on the vector chromatic number (and thus the chromatic number) using the spectrum of the non-backtracking walk matrix, and an upper bound dependent only on the girth and universal cover. Our upper bound may be equivalently viewed as a generalization of the Alon-Boppana theorem to irregular graphs
Download