Algebras, graphs and thetas
arXiv:1910.06260 · doi:10.1016/j.entcs.2019.08.025
Abstract
We extend the clique-coclique inequality, previously known to hold for graphs in association schemes and vertex-transitive graphs, to graphs in homogeneous coherent configurations and 1-walk regular graphs. We further generalize it to a stronger inequality involving the Lovász theta number of such graphs, and some theta variants, including characterizations of the equality.
A version of this paper is published on the proceedings of LAGOS 2019