\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Ji\v{r}\'{\i} Matou\v{s}ek and Robert \v{S}\'amal}
%
%
\medskip
\noindent
%
%
{\bf Induced Trees in Triangle-Free Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
We prove that every connected triangle-free graph on $n$ vertices contains
an induced tree on $\exp(c\sqrt{\log n}\,)$ vertices, where $c$ is  
a positive constant. The best known upper bound is $(2+o(1))\sqrt n$. 
This partially answers questions of Erd\H{o}s, Saks, and S\'os and of Pultr.

\bye