Explicit Ramsey graphs and orthonormal labelings

Noga Alon

The electronic journal of combinatorics, Tome 1 (1994)

Résumé

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 on $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 $R^n$, so that among any three of them some two are orthogonal, is $\Theta(n^{2/3})$.

Détail

DOI : 10.37236/1192

Classification : 05C55, 05C78, 05C35
Mots-clés : Ramsey graphs, orthonormal labelings, Lovász function, triangle-free graphs, independent sets