\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4
Abstract for Noga Alon, Explicit Ramsey graphs and orthonormal labelings


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\'asz
$\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})$.




\bye