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.
arXiv commentA version of this paper is published on the proceedings of LAGOS 2019