zbMATH — the first resource for mathematics

Explicit Ramsey graphs and orthonormal labelings. (English) Zbl 0814.05056
Electron. J. Comb. 1, Research paper R12, 8 p. (1994); printed version J. Comb. 1, 171-178 (1994).
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})\).

05C55 Generalized Ramsey theory
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C35 Extremal problems in graph theory