# 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})$$.

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