Balla, I;
Letzter, S;
Sudakov, B;
(2020)
Orthonormal Representations of H-Free Graphs.
Discrete & Computational Geometry
, 64
pp. 654-670.
10.1007/s00454-020-00185-0.
Preview |
Text
main.pdf - Accepted Version Download (418kB) | Preview |
Abstract
Let x1,…,xn∈Rd 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 x1+⋯+xn 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 ϑ-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 ϑ(G¯¯¯¯) over all H-free graphs G.
| Type: | Article |
|---|---|
| Title: | Orthonormal Representations of H-Free Graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/s00454-020-00185-0 |
| Publisher version: | https://doi.org/10.1007/s00454-020-00185-0 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Lovász ϑ-function, Minrank, Orthonormal representation, Turán numbers |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10107281 |
Archive Staff Only
 |
View Item |
