Orthonormal representations of $H$-free graphs

Abstract

Let $x_1,\dots ,x_n\in {\mathbb{R}}^d$ be unit vectors such that among any three there is an orthogonal pair. How large can $n$ be as a function of $d$, and how large can the length of $x_1+\dots +x_n$ be? The answers to these two celebrated questions, asked by Erdős and Lovász, are closely related to orthonormal representations of triangle-free graphs, in particular to their Lovász $\vartheta$-function and minimum semidefinite rank. In this paper, we study these parameters for general $H$-free graphs. In particular, we show that for certain bipartite graphs $H$, there is a connection between the Turán number of $H$ and the maximum of $\vartheta \left(\overline{G}\right)$ over all $H$-free graphs $G$.

16 pages