- Journal Article
Let x(1), ... , x(n) is an element of R-d be unit vectors such that among any three there is an orthogonal pair. Howlarge can n be as a function of d, and howlarge can the length of x(1)+ ... + x(n) be? The answers to these two celebrated questions, asked by Erdos and Lovasz, are closely related to orthonormal representations of triangle-free graphs, in particular to their Lovasz.-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 Turan number of H and the maximum of v((G) over bar) over all H-free graphs G. Show more
Journal / seriesDiscrete & Computational Geometry
Pages / Article No.
SubjectLovasz v-function; Minrank; Orthonormal representation; Turan numbers
Organisational unit03993 - Sudakov, Benjamin / Sudakov, Benjamin
175573 - Extremal problems in combinatorics (SNF)
MoreShow all metadata