Orthonormal representations of $H$-free graphs

Let $x_1, \ldots, 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 + \ldots + 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$.

No reviews yet.

No comments yet.