Explicit Ramsey graphs and orthonormal labelings (Q1346731)

Summary: We describe an explicit construction of triangle-free graphs with no independent sets of size \(m\) and with \(\Omega(m^{3/2})\) vertices, improving a sequence of previous constructions by various authors. As a byproduct we show that the maximum possible value of the Lovász \(\theta\)-function of a graph of \(n\) vertices with no independent set of size 3 is \(\Theta(n^{1/3})\), slightly improving a result of Kashin and Konyagin who showed that this maximum is at least \(\Omega(n^{1/3}/\log n)\) and at most \(O(n^{1/3})\). Our results imply that the maximum possible Euclidean norm of a sum of \(n\) unit vectors in \(\mathbb{R}^ n\), so that among any three of them some two are orthogonal, is \(\Theta(n^{2/3})\).