A Lovász Theta Bound for a Graph Saturation Parameter

Abstract

For a finite simple graph G on n vertices, let μ(G) be the minimum trace of a real symmetric matrix X satisfying 0 ≼ X ≼ I, Xᵢⱼ = 0 on the edges of G, and ⟨J,X⟩ = n. We prove that μ(G) ≤ ϑ(complement G) for every G, answering affirmatively question (iii) in Section 7 of Carli Silva, Coutinho, Oliveira, and Tunçel, arXiv:2609.06312v1. The proof maximizes the sum of logarithms of the coordinates over the theta body. A supporting inequality at the maximizer yields a spectral contraction after diagonal scaling of any witness matrix. The same supporting inequality, applied to a constant point supplied by the complementary theta dual, bounds the trace of the resulting feasible matrix. Version 1 contains the four-page preprint and its complete editable LaTeX source. The manuscript discloses extensive AI assistance in developing and checking the proof and preparing the text. The checks are internal and do not constitute external peer review.