A connection between the A-spectrum and Lovász theta number

We show that the smallest α so that α D + ( 1 − α ) A ≽ 0 is at least 1 / ϑ ( G ‾ ) , significantly improving upon a result due to Nikiforov and Rojo (2017). In fact, we display a stronger connection: if the nonzero entries of A are allowed to vary and those of D vary accordingly, then we show that this smallest α is in fact equal to 1 / ϑ ( G ‾ ) . We also show other results obtained as an application of this optimization framework, including a connection to the well-known quadratic formulation for ω ( G ) due to Motzkin and Straus (1964).