%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  PlainTeX source file for the paper 
%
% `The size-Ramsey number of trees'
%
%  by P.E. Haxell and Y. Kohayakawa 
%  
%  for the Israel Journal of Mathematics 
%
%  7 December, 1993
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Remark: the TeX specifications of the IJM are after the macros. 
%  (Search for `specifications')
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\magnification=\magstep1
\newcount\spcounter
\def\setupspacing{\afterassignment\setupsp\spcounter}
\def\setupsp{\ifcase\spcounter
\baselineskip=\normalbaselineskip
\smallskipamount=\smallskipamount
\medskipamount=\medskipamount
\bigskipamount=\bigskipamount
\or
\baselineskip=1.38\normalbaselineskip
\smallskipamount=1.38\smallskipamount
\medskipamount=1.38\medskipamount
\bigskipamount=1.38\bigskipamount
\or
\baselineskip=1.53\normalbaselineskip     
\smallskipamount=1.53\smallskipamount     
\medskipamount=1.53\medskipamount         
\bigskipamount=1.53\bigskipamount
\or
\baselineskip=1.67\normalbaselineskip     
\smallskipamount=1.67\smallskipamount     
\medskipamount=1.67\medskipamount         
\bigskipamount=1.67\bigskipamount
\fi}
\setupspacing1
\input mssymb
\font\ninerm=cmr9   \font\eightrm=cmr8       \font\sixrm=cmr6
\font\ninei=cmmi9   \font\eighti=cmmi8       \font\sixi=cmmi6
\font\ninesy=cmsy9  \font\eightsy=cmsy8      \font\sixsy=cmsy6
\font\ninebf=cmbx9   \font\eightbf=cmbx8     \font\sixbf=cmbx6
\font\ninett=cmtt9   \font\eighttt=cmtt8
\font\nineit=cmti9   \font\eightit=cmti8
\font\ninesl=cmsl9   \font\eightsl=cmsl8
\font\ninemsa=msam9  \font\eightmsa=msam8 \font\sixmsa=msam6
\font\ninemsb=msbm9  \font\eightmsb=msbm8 \font\sixmsb=msbm6
\def\deffont{\bf} % as required by IJM
%\def\deffont{\it} % usual
% the following \ninepoint and \eightpoint come from the TeXbook
\def\ninepoint{\def\rm{\fam0\ninerm}%
\textfont0=\ninerm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
\textfont1=\ninei  \scriptfont1=\sixi  \scriptscriptfont1=\fivei
\textfont2=\ninesy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
\textfont3=\tenex  \scriptfont3=\tenex  \scriptscriptfont3=\tenex
\textfont\itfam=\nineit \def\it{\fam\itfam\nineit}%
\textfont\slfam=\ninesl \def\sl{\fam\slfam\ninesl}%
\textfont\ttfam=\ninett \def\tt{\fam\ttfam\ninett}%
\textfont\bffam=\ninebf \scriptfont\bffam=\sixbf
 \scriptscriptfont\bffam=\fivebf \def\bf{\fam\bffam\ninebf}%
\textfont\msafam=\ninemsa  \scriptfont\msafam=\sixmsa
  \scriptscriptfont\msafam=\fivemsa
\textfont\msbfam=\ninemsb  \scriptfont\msbfam=\sixmsb
  \scriptscriptfont\msbfam=\fivemsb
%\tt\ttglue=.5em plus.25em minus.15em
\normalbaselineskip=11.7pt
\setbox\strutbox=\hbox{\vrule height8pt depth3pt width0pt}%
\let\sc=\sevenrm%\let\big=\ninebig
\normalbaselines\rm}
\def\eightpoint{\def\rm{\fam0\eightrm}%
\textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
\textfont1=\eighti  \scriptfont1=\sixi  \scriptscriptfont1=\fivei
\textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
\textfont3=\tenex  \scriptfont3=\tenex  \scriptscriptfont3=\tenex
\textfont\itfam=\eightit \def\it{\fam\itfam\eightit}%
\textfont\slfam=\eightsl \def\sl{\fam\slfam\eightsl}%
\textfont\ttfam=\eighttt \def\tt{\fam\ttfam\eighttt}%
\textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
 \scriptscriptfont\bffam=\fivebf \def\bf{\fam\bffam\eightbf}%
\textfont\msafam=\eightmsa  \scriptfont\msafam=\sixmsa
  \scriptscriptfont\msafam=\fivemsa
\textfont\msbfam=\eightmsb  \scriptfont\msbfam=\sixmsb
  \scriptscriptfont\msbfam=\fivemsb
%\tt\ttglue=.5em plus.25em minus.15em
\normalbaselineskip=10pt
\setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
\let\sc=\sixrm%\let\big=\eightbig
\normalbaselines\rm}
\font\twelverm=cmr12
\font\twelvebf=cmbx12
\font\twelveit=cmti12
\font\twelvesl=cmsl12
\let\centreline=\centerline
\def\enddiscard{}
\long\def\discard#1\enddiscard{}
\def\date{\number\day\space
  \ifcase\month\or January\or February\or March\or April\or May\or June
               \or July\or August\or September\or November\or December\fi,
  \number\year}
%
% further maths macros
%
\def\N{{\Bbb N}}
\def\Z{{\Bbb Z}}
\def\R{{\Bbb R}}
\def\E{{\Bbb E}}
\def\P{{\Bbb P}}
\def\e{{\rm e}}
\def\Bi{\mathop{\rm Bi}\nolimits}
\def\symmdiff{\bigtriangleup}
\def\im{\mathop{\rm im}\nolimits}
\def\mod{\mathop{\rm mod}}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\<{\left\langle}
\xdef\:{\>}
\def\>{\right\rangle}  % This is different from TeX  :( 
\def\lbr{\left\{}
\def\rbr{\right\}}
\def\setof#1{\left\{#1\right\}}
\def\sizeof#1{\left|#1\right|}
\def\comp{^{\rm c}}
\def\superset{\supset}
%
\newcount\eqnocounter
\eqnocounter=0
\def\slabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  \eqno({\number\eqnocounter})}
\def\alabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  ({\number\eqnocounter})}
%
\font\titlefont=cmbx10 scaled \magstep1
\def\authorfont{\rm}
\def\addressfont{\rm}
\def\title#1{\null\vglue5truecm{\parindent=0pt\titlefont#1}}
\def\titlecont#1{\vskip.3pt{\parindent=0pt\titlefont#1}}
\def\author#1{{\authorfont\vglue1.7truecm\noindent#1}}
\def\Fapesp{${}^*$\footnote\null{{\eightpoint${^*}$ Research supported by
                                    FAPESP, Brazil, Proc.\ MAP 86/0904--8}}}
\def\NSF{\footnote{${}^{\hbox{\dag}}$}{{\eightpoint Partially
                             supported by NSF grant DMS-8806097}}}
\def\endaddress{\par\endgroup}
\def\address#1\endaddress{\medskip\begingroup
               \eightpoint\baselineskip=9pt
               \noindent\raggedright\addressfont#1\endaddress}
\newif\ifemailwanted
\emailwantedfalse
\def\DPMMS{Department of Pure Mathematics
           and Mathematical Statistics, \hfill\break
           University of Cambridge, 16 Mill Lane, Cambridge
           CB2~1SB, England\ifemailwanted\hfill\break\vskip1\jot
           \noindent{\tt e-mail: yk101@phx.cam.ac.uk}\hfill\fi}
\def\IMEUSP{Instituto de Matem\'atica e Estat\'\i stica, Universidade
            de S\~ao Paulo, \hfill\break
            Caixa Postal~20570, 01452--990~S\~ao Paulo, SP, Brazil}
\def\draftdate{\vglue1truecm\noindent{\eightpoint\rm Draft of \date}}
\newif\ifdraft
\newif\ifexplicitdate
\def\draftof#1{\drafttrue\explicitdatetrue\def\givendate{#1}}
\explicitdatefalse
\draftfalse
\headline={\ifdraft\hfil{\eightpoint{\sl draft of %
\ifexplicitdate\givendate\else\date\fi}}\else\hfil\fi}
\def\endabstract{\par\endgroup}
\def\abstract{\vglue1.3truecm\begingroup
  \ninepoint\noindent{\bf Abstract.\enspace}\ignorespaces}
\def\endfinalnotes{\par\endgroup}
\def\finalnotes#1.{\bigbreak\begingroup
  \eightpoint\noindent{\bf #1.\enspace}\ignorespaces}
\outer\def\proclaim #1. {%\message{#1 }
  \medbreak\noindent{\bf#1.\enspace}\bgroup\sl\ignorespaces}
\def\endproclaim{\par\egroup\ifdim\lastskip<\medskipamount\removelastskip
                                \penalty1000\medskip\fi}
\outer\def\endproclaimsquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
 \egroup\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}
\def\endclaim{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\long\def\claim{\smallbreak
\noindent  
{\it Claim.\enspace}\ignorespaces\bgroup\sl}
\def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\def\endassertionsquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}
 \egroup\par\ifdim\lastskip<\smallskipamount\removelastskip\penalty20\smallskip\fi}
\long\def\assertion(#1){\smallbreak
\noindent 
{\rm(}{#1}{\rm)}\enspace\ignorespaces\bgroup\sl}
\def\endcase{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty3000\smallskip\fi}
\def\case#1.{\smallbreak
\noindent 
{\sl Case\/} #1.\enspace\ignorespaces}
\def\casenodot#1 {\smallbreak
\noindent 
{\sl Case\/} #1\enspace\ignorespaces}
\def\endcasebody{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\outer\def\endcasebodysquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
    {\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}}
\def\casebody{\noindent\ignorespaces}
\let\proofofassertion=\casebody
\let\endproofofassertion=\endcasebody
\let\endproofofassertionsquare=\endcasebodysquare
\def\proofoftheclaim{\proofofassertion{\it Proof of the Claim\/}.\enspace}
\let\endproofoftheclaim=\endproofofassertion
\def\square{\ifmmode\sqr\else{$\sqr$}\fi}
\def\sqr{\vcenter{
         \hrule height.1mm
         \hbox{\vrule width.1mm height2.2mm\kern2.18mm\vrule width.1mm}
         \hrule height.1mm}}                  % This is a slimmer sqr.
\outer\def\endproofnoskip{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}}% TeXbook, p 106.
\outer\def\endproofsmallskip{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
    {\ifdim\lastskip<\smallskipamount\removelastskip\penalty-10\smallskip\fi}}
\outer\def\endproof{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
    {\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}}
\outer\def\endproofnosquare{\removelastskip\penalty-10\bigskip}
\let\endproofoftheclaimsquare=\endproof
\outer\def\proof{%
   \ifdim\lastskip<\medskipamount\removelastskip\penalty1000\medskip\fi
   \noindent{\it Proof.\enspace}\ignorespaces}
\outer\def\proofof#1.{%
   \ifdim\lastskip<\medskipamount\removelastskip\penalty60\medskip\fi
   \noindent{\it Proof of} {#1}.\enspace\ignorespaces}
\outer\def\proofofnodot#1 {%
   \ifdim\lastskip<\medskipamount\removelastskip\penalty60\medskip\fi
   \noindent{\it Proof of\/} {#1}\enspace\ignorespaces}
\newif\iflargesectiontitles
\largesectiontitlesfalse
\def\beginsection#1\par{\vskip0pt plus.08\vsize\penalty-250
    \vskip0pt plus-.08\vsize\bigskip\vskip\parskip
    %\message{#1}
    \leftline{\iflargesectiontitles\twelvebf\else\bf\fi#1}%
    \nobreak\smallskip\noindent}
\def\ititem(#1){\item{({\it#1})}}
\def\ititemnohangindent(#1){\par\textindent{({\it#1\/})}}
\def\itemnohang#1{\par\textindent{#1}}
\let\TeXiff=\iff
\def\iff{\ifmmode\TeXiff\else if{}f\fi}
%
% Macros for references
%
\newif\ifPortuguese
\newif\iffirstgo
\Portuguesefalse
\def\scanreferences{\firstgotrue\refno=0\beginreferences%
                       \input refs\endreferences}%
\def\shipoutreferences{\firstgofalse\refno=0
                       \beginreferences\input refs\endreferences}
\def\endreferences{\par\endgroup}
\outer\def\beginreferences
   {\begingroup\iffirstgo\else\pretolerance=1000\tolerance=3000
    %\raggedright
    \frenchspacing
    %\vskip0pt plus.3\vsize\penalty-150\vskip0pt plus-.3\vsize
    %\bigskip\vskip\parskip
    \vskip0pt plus.1\vsize\penalty-250
    \vskip0pt plus-.08\vsize\bigskip\vskip\parskip
    %\message{References}
    \ifPortuguese\leftline{\iflargesectiontitles
                             \twelvebf\else\bf\fi Refer\^encias}%
             \else\leftline{\iflargesectiontitles
                              \twelvebf\else\bf\fi References}\fi
    \nobreak\smallskip\ninepoint\fi\obeylines}
% Journals
\def\BLMS{Bull. London Math. Soc.}
\def\JAMS{J. Amer. Math. Soc.}
\def\JLMS{J. London Math. Soc.}
\def\PLMS{Proc. London Math. Soc.}
\def\JCT{J. Combinatorial Theory}
\def\JCTA{J. Combinatorial Theory~(A)}
\def\JCTB{J. Combinatorial Theory~(B)}
\def\JGT{J. Graph Theory}
\def\Comb{Combinatorica}
\def\AMASH{Acta Math. Acad. Sci. Hungar.}
\def\SSMH{Studia Sci. Math. Hung.}
\def\EJC{Europ. J. Combinatorics}
\def\GC{Graphs and Combinatorics}
\def\IJM{Israel J. Math.}
\def\DM{Discrete Math.}
\def\ADM{Ann. Discrete Math.}
\def\TAMS{Trans. Amer. Math. Soc.}
\def\PAMS{Proc. Amer. Math. Soc.}
\def\PMH{Periodica Math. Hungar.}
\def\PCPS{Proc. Cambridge Phil. Soc.}
\def\MPCPS{Math. Proc. Cambridge Phil. Soc.}
\def\RSA{Random Structures and Algorithms}
% Authors
\def\Aj{Ajtai, M.}
\def\Al{Alon, N.}
\def\Be{Beck, J.}
\def\BB{Bollob\'as, B.}
\def\Chung{Chung, F.R.K.}
\def\Er{Erd\H os, P.}
\def\Fr{Frankl, P.}
\def\Fu{F\"uredi, Z.}
\def\Gra{Graham, R.L.}
\def\Ka{Katona, G.O.H.}
\def\Kl{Kleitman, D.J.}
\def\Ko{Koml\'os, J.}
\def\Lo{Lov\'asz, L.}
\def\Ne{Ne\v set\v ril, J.}
\def\Po{P\'osa, L.}
\def\Ro{R\"odl, V.}
\def\Sey{Seymour, P.}
\def\Sh{Shearer, J.B.}
\def\Si{Simonovits, M.}
\def\So{S\'os, V.T.}
\def\Sp{Spencer, J.H.}
\def\Sz{Szemer\'edi, E.}
\def\Tur{Tur\'an, P.}
\def\Tutte{Tutte, W.T.}
\def\Tu{Tuza, Zs.}
%
\newcount\refno
\def\vol{}
\begingroup
\obeylines
\long\global\def\paper[#1] #2
#3
#4\vol#5
#6, #7
{\global\advance\refno by1%
 \iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
  \else\smallskip\item{[\number\refno]} %
#2, #3, {\it#4}~{\bf#5} (#7), \hbox{#6}.\fi}%
\global\def\proceedings[#1] #2
#3
#4
#5
#6
#7
{\global\advance\refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, #3, {\it in} {``#4''}, #5 (#6 eds), %
\hbox{#7}.\fi}%
\global\def\book[#1] #2
#3
#4
{\global\advance\refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
          \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%
 \else\smallskip\item{[\number\refno]} #2, {\it #3\/}, #4.\fi}%
\global\def\preprint[#1] #2
#3
#4
{\global\advance\refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, #3, #4.\fi}%
\global\def\privatecomm[#1] #2
{\global\advance \refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, private communication.\fi}%
\global\def\unpublished[#1] #2
{\global\advance \refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, unpublished.\fi}%
\global\def\dammit[#1] #2
#3
{\global\advance \refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, #3.\fi}%
\endgroup 
%
% statems 
%
\newif\ifchapters
\chapterstrue
\newcount\chapterno\chapterno=0
\newcount\statemno\statemno=1
\def\yeschapters{\def\statementlabel{%\number\chapterno.
                                      \number\statemno}
              \def\newchapter{\statemno=1\advance\chapterno by1}}
\def\nochapters{\def\statementlabel{\number\statemno}
                \def\newchapter{\relax}}
\ifchapters\yeschapters\else\nochapters\fi
\def\newstatemno{\advance\statemno by1}
\edef\TreeUniv
{\statementlabel}\newstatemno
\edef\lemmaA
{\statementlabel}\newstatemno
\edef\lemmaB
{\statementlabel}\newstatemno
\edef\CorC
{\statementlabel}\newstatemno
\edef\TechLemma
{\statementlabel}\newstatemno
\edef\TechLemmaB
{\statementlabel}\newstatemno
\edef\BeckLemma
{\statementlabel}\newstatemno
\edef\MainResA
{\statementlabel}\newstatemno
\edef\MainResB
{\statementlabel}\newstatemno
\edef\CorSizeR
{\statementlabel}\newstatemno
%
% macros
%
\let\phi=\varphi 
\def\G{{\cal G}}
\def\cP{{\cal P}}
\def\dbar{\bar d}
%\def\darrows#1{\mathrel{\mathop{\longrightarrow}\limits_{#1}}}
\def\darrows#1{\to_{#1}}
\def\sizeR{r_{\rm e}}
\def\Bi{\mathop{\rm Bi}\nolimits}
\let\epsilon=\varepsilon
%
% \scanreferences
%
\firstgotrue\refno=0\beginreferences
\paper[Alon] \Al
            Eigenvalues, geometric expanders, sorting in rounds, %
            and Ramsey theory
            \Comb\vol6
            207--219, 1986
\dammit[Apc] \Al
            Personal communication, August~1993
\paper[AC]  \Al, \Chung
            Explicit construction of linear sized tolerant networks 
            \DM\vol72
            15--19, 1988
\paper[AGHP] \Al, Goldreich, O., H\aa stad, J., Peralta, R.
            Simple constructions of almost $k$-wise %
            independent random variables
            \RSA\vol3
            289--304, 1992
\dammit[AR] \Al, Roichman, Y.
            Random Cayley graphs and expanders, to appear
\paper[Beck] \Be
            On size Ramsey number of paths, trees, and circuits~I
            \JGT\vol7
            115--129, 1983
\dammit[BeckB] \Be 
            On size Ramsey number of paths, trees, and circuits~II, %
            in {\it Mathematics of Ramsey Theory\/}  (\Ne, \Ro, eds), %
            Algorithms and Combinatorics~5, Springer-Verlag, %
            Berlin~1990, pp.~34--45
\book[BBf]  \BB
            Random Graphs
            Academic Press, London, 1985, ${\it xvi}+447$pp
\paper[Bomb] Bombieri, E.
            On the large sieve
            Mathematika\vol12
            201--225, 1965
\book[Dave] Davenport, H.
            Multiplicative Number Theory,~{\rm Second edition, %
            Graduate Texts in Mathematics~74}
            Springer--Verlag, New York~1980, ${\it xiv}+177$pp
\paper[FP]  Friedman, J., Pippenger, N.
            Expanding graphs contain all small trees
            \Comb\vol7
            71--76, 1987
\dammit[HKb] Haxell, P.E., Kohayakawa, Y.
            On an anti-Ramsey property of Ramanujan graphs, to appear
\paper[Hoeff] Hoeffding, W. 
            Probability inequalities for sums of bounded random %
            variables  
            Jour. Amer. Statistical Assoc.\vol58 
            13--30, 1963
\paper[Ke]  Ke, X. 
            The size Ramsey number of trees with bounded degree
            \RSA\vol4
            85--97, 1993
\dammit[Lo] \Lo
            {\it Combinatorial Problems and Exercises\/}, %
            North Holland, Amsterdam~1979
\paper[LPS] Lubotzky, A., Phillips, R., Sarnak, P.
            Ramanujan graphs
            \Comb\vol8
            261--277, 1988
\dammit[McD] McDiarmid, C.J.H. 
            On the method of bounded differences, in {\sl Surveys in %
            Combinatorics~1989\/} (Siemons, J., ed.), London %
            Mathematical Society Lecture Notes Series~141, Cambridge %
            University Press, Cambridge~1989, pp.~148--188
\endreferences
% 
% specifications of the IJM
%
\parindent=1em
\baselineskip=15pt
\hsize=12.3cm
\vsize=18.5cm
\let\qed=\endproof % The proofs end with \qed 
                   % (a square justified right)
\def\colon{{:}\;}
%
\hoffset=.9truecm 
%
% fstpg
%
\title{The Size-Ramsey Number of Trees}

\author{P.E.~Haxell${}^{1*}$ and Y.~Kohayakawa${}^2$}
\address
${}^1$\DPMMS\medskip
\noindent${}^2$\IMEUSP%
\footnote\null
{\eightpoint1991 {\it Mathematics Subject
  Classification\/}~05$\,$C$\,$55, 05$\,$C$\,$05, 05$\,$C$\,$80}
\footnote\null
{\eightpoint${}^*${\sl Current address\/}: Department of Combinatorics 
and Optimisation, University of Waterloo, Waterloo, Ontario, Canada 
N2L~3G1}
\footnote\null
{\eightpoint The first author was partially supported by NSERC.  The
second author was partially supported by FAPESP (Proc.~93/0603-1) and
by CNPq (Proc.~300334/93--1).}
\endaddress
\abstract
If~$G$ and~$H$ are graphs, let us write~$G\to(H)_2$ if~$G$ contains
a monochromatic copy of~$H$ in any $2$-colouring of the edges of~$G$. 
The {\deffont size-Ramsey number\/}~$\sizeR(H)$ of a graph~$H$ is the
smallest possible number of edges a graph~$G$ may have if~$G\to(H)_2$.
Suppose~$T$ is a tree of order~$|T|\geq2$, and let~$t_0$, $t_1$ be the
cardinalities of the vertex classes of~$T$ as a bipartite graph, and
let~$\Delta(T)$ be the maximal degree of~$T$.
Moreover, let~$\Delta_0$, $\Delta_1$ be the maxima of the
degrees of the vertices in the respective vertex classes, and
let~$\beta(T)=t_0\Delta_0+t_1\Delta_1$. 
Beck~{\refBeckB} proved
that~$\beta(T)/4\leq\sizeR(T)=O\{\beta(T)(\log|T|)^{12}\}$, improving
on a previous result of his~{\refBeck} stating
that~$\sizeR(T)\leq\Delta(T)|T|(\log|T|)^{12}$.
In~{\refBeck}, Beck conjectures that~$\sizeR(T)=O\{\Delta(T)|T|\}$,
and in~{\refBeckB} he puts forward the stronger conjecture
that~$\sizeR(T)=O\{\beta(T)\}$.
Here, we prove the first of these conjectures, and come quite close to
proving the second by showing
that~$\sizeR(T)=O\{\beta(T)\log\Delta(T)\}$.
\endabstract
% 
% intro
% 
\beginsection 1. Introduction

In this note we are concerned with a numerical problem in Ramsey
theory: we shall study the size-Ramsey number of trees.  
Before we proceed, let us
introduce some notation and definitions. 
For a graph~$G$, we write~$|G|$ for
the {\deffont order\/}~$|V(G)|$ of~$G$, and~$e(G)$ for its {\deffont
size\/}~$e(G)$.  
Let a real~$0\leq\gamma\leq1$ and an integer~$r\geq2$ be
fixed, and suppose~$G$ and~$H$ are graphs. 
We write~$G\darrows\gamma H$ if any
subgraph~$J\subset G$ of~$G$ with size~$e(J)\geq\gamma e(G)$ contains an
isomorphic copy of~$H$ as a subgraph, and we write~$G\to(H)_r$ if~$G$
contains a monochromatic copy of~$H$ in any edge-colouring of~$G$
with~$r$ colours. 

Settling a one-hundred-dollar problem of Erd\H os, ten years ago
Beck~{\refBeck} proved the following striking result. 
Let~$P^t$ be the path of
order~$t$. 
If~$0<\gamma\leq1$ and~$p=C_\gamma/n$, where~$C_\gamma>0$ is a
constant that depends only on~$\gamma$, then the random
graph~$G_p=G_{n,p}\in\G(n,p)$ is almost surely such
that~$G\darrows\gamma P^t$ for~$t=\lfloor C_\gamma^{-1}n\rfloor$. 
As an immediate corollary, one has that
for any fixed~$r\geq2$ the {\deffont$r$-size-Ramsey number\/}
$$
\sizeR(H,r)=\min\{e(G)\colon G\to(H)_r\}  \slabel{sRdef}
$$
of the path~$H=P^t$ is~$O(c_rt)$ for some constant~$c_r$ that depends
only on~$r$. 
Also in~{\refBeck}, Beck shows by non-constructive means that the
size-Ramsey number~$\sizeR(T)=\sizeR(T,2)$ of a tree~$T=T^t$ of
order~$t$ and maximal degree~$\Delta=\Delta(T)$ is not greater
than~$\Delta t(\log t)^{12}$. 
(The proof of this result is complex and it is heavily based on
the probabilistic method: besides random graphs, the Erd\H
os--Lov\'asz sieve is used.)  
Thus, for trees
of bounded maximal degree, the size-Ramsey number is nearly linear
in~$|T|$. 
Indeed, Beck conjectures in~{\refBeck} that~$\sizeR(T)=O\{\Delta(T)|T|\}$.

More recently, Friedman and Pippenger~{\refFP} improved on Beck's
result by showing that, for trees~$T$ of bounded maximal degree, it
does indeed hold that the size-Ramsey number~$\sizeR(T)$ is linear
in~$|T|$.   
The proof in~{\refFP} is based on a new, beautiful tree-universality
result for expanding graphs. 
With this result in hand, basically following Alon and
Chung~{\refAC} and Beck~{\refBeck}, Friedman and Pippenger~{\refFP}
prove the following result.  
Let~$0<\gamma\leq1$, and~$1\leq\Delta<t$ be given. 
Then, for suitable primes~$p$ and~$q$, the Ramanujan graph~$X=X^{p,q}$
constructed by Lubotzky, Phillips, and Sarnak~{\refLPS} is such that
({\it i\/})~$e(X)\leq c\Delta^4\gamma^{-3}t$, where~$c$ is an absolute
constant, and ({\it ii\/})~$X\darrows\gamma T$ for any tree~$T$ of
order~$|T|\leq t$ and maximal degree~$\Delta(T)\leq\Delta$. 
Note that this is a `density' type
result rather than a Ramsey-theoretical one, by which we mean that it
concerns the property~$G\darrows\gamma T$ rather than~$G\to(T)_r$.  
Clearly, the Friedman--Pippenger result above implies
that~$\sizeR(T)=O\{\Delta(T)^4|T|\}$ for any tree~$T$. 
This bound has very recently been improved by Ke~{\refKe},
who proved a density type result implying
that~$\sizeR(T)=O\{\Delta(T)^2|T|\}$. 
Our first main result in this note,
Theorem~{\MainResB} (see also Corollary~{\CorSizeR}), improves this 
to~$\sizeR(T)=O\{\Delta(T)|T|\}$, thus verifying the conjecture of
Beck~{\refBeck}.

Now, note that if~$T$ is the $(t-1)$-star~$K^{1,t-1}$ ($t\geq2$), then
clearly~$\sizeR(T)=2t-3$, whereas~$\Delta(T)|T|=t(t-1)$.  
Thus the bound~$\sizeR(T)=O\{\Delta(T)|T|\}$ may be far from sharp for
some trees~$T$. 
Beck~{\refBeckB} has identified what seems to be the `correct'
parameter of a tree~$T$ that determines the order of~$\sizeR(T)$.  
If~$T$ has bipartition~$V(T)=V_0(T)\cup V_1(T)$
and~$t_\sigma=|V_\sigma(T)|$,
$\Delta_\sigma=\Delta_\sigma(T)=\max\{d(v)\colon v\in V_\sigma(T)\}$ 
($\sigma\in\{0,1\}$), let~$\beta(T)=t_0\Delta_0+t_1\Delta_1$. 
Note that for instance~$\beta(K^{1,t-1})=2(t-1)$ and
moreover~$\beta(T)\leq\Delta(T)|T|$ for any tree~$T$. 
Improving his previous result, Beck~{\refBeckB} proved that
$$
\beta(T)/4\leq\sizeR(T)\leq C\beta(T)(\log|T|)^{12}   \slabel{Beck}
$$
for any tree~$T$ and some absolute constant~$C$, and thus
determined~$\sizeR(T)$ up to a~$(\log|T|)^{12}$ factor.  
Beck conjectures in~{\refBeckB} that the lower bound in~{\eqnoBeck}
gives the correct order of~$\sizeR(T)$, {\it
  i.e.\/}~that~$\sizeR(T)=O\{\beta(T)\}$.  
We are unable to prove this conjecture, but here we considerably
improve the upper bound in~{\eqnoBeck} by showing that~$\sizeR(T)\leq
C\beta(T)\log\Delta(T)$ for some absolute constant~$C$. 
Furthermore, the result of Beck that gives the upper
bound in~{\eqnoBeck} is intrinsically Ramsey-theoretical, whereas ours
is a density type result.

Our method is based on the Friedman--Pippenger tree-universality
result. 
We in fact obtain a variant of that result using the same
argument, and then we show how our bounds follow from this variant and
a simple result concerning random bipartite graphs. 
Our methods are non-constructive owing to the use of random graphs, 
but we remark that, for most trees~$T$, there are explicit
constructions of graphs~$G$ that give~$\sizeR(T)=O\{\Delta(T)|T|\}$. 
These constructions are based on the Ramanujan graphs~$X^{p,q}$ of
Lubotzky, Phillips, and Sarnak~{\refLPS}, and certain Cayley graphs of
Abelian groups due to Alon~{\refApc}.  
For trees~$T$ with~$\Delta(T)$ about~$|T|^{1-1/d}$ for some
integer~$d\geq2$, we may prove that~$\sizeR(T)=O\{\Delta(T)|T|\}$
constructively by considering projective geometries. 
(See Section~5). 

This note is organised as follows. 
Our variant of Friedman and Pippenger's tree-universality result is
stated and proved in Section~2, and in the following section we give
the results concerning random bipartite graphs that we need. 
For the inequalities used in Section~3 as well as for definitions not
given here in detail, we refer the reader to~{\refBBf}. 
In Section~4 we prove our main results. 
Comments concerning explicitly constructed graphs that may replace
the random graphs used in our proofs are given in Section~5.
%
% sec2
%
\beginsection 2. A tree-universality result

We shall assume throughout that all our bipartite graphs have been given a
fixed bipartition. 
More specifically, if~$G$ is a bipartite graph, its
associated bipartition will be~$V(G)=V_0(G)\cup V_1(G)$. 
In particular, if~$T$ is a tree of order~$t=|T|\geq2$, we assume fixed
one of the canonical bipartitions~$V(T)=V_0(T)\cup V_1(T)$ of~$T$.   
Also, if~$G$ is a bipartite graph with associated
bipartition~$V(G)=V_0(G)\cup V_1(G)$, we
let~$\Delta_\sigma(G)=\max\{d_G(v)\colon v\in V_\sigma(G)\}$ and
put~$n_\sigma(G)=|V_\sigma(G)|$ ($\sigma\in\{0,1\}$).   
We sometimes write~$G=G^{n_0,n_1}$ if~$n_\sigma(G)=n_\sigma$
($\sigma\in\{0,1\}$). 
If~$T$ is a tree, and~$\Delta_\sigma(T)\leq\Delta_\sigma$,
$n_\sigma(T)\leq t_\sigma$ ($\sigma\in\{0,1\}$), we say that~$T$ is a 
$(t_0,\Delta_0;t_1,\Delta_1)$-{\deffont tree\/}.

Now let~$J$ be a bipartite graph with associated
bipartition~$V(J)=V_0(J)\cup V_1(J)$.  
If for every~$X\subset V_\sigma(J)$ with~$|X|\leq
b_\sigma$ ($\sigma\in\{0,1\}$) we have~$|\Gamma_J(X)|\geq
f_\sigma|X|$, we say that~$J$ is a
{\deffont$(b_0,f_0;b_1,f_1)$-expanding\/} bipartite graph.  
The main result in this section is the following.

\proclaim Theorem {\TreeUniv}. 
Suppose~$1\leq\Delta_0\leq t_1$ and~$1\leq\Delta_1\leq t_0$ are fixed
integers.  
Then every non-empty
$(2t_1/\Delta_0,2\Delta_0;2t_0/\Delta_1,2\Delta_1)$-expanding
bipartite graph contains as a subgraph
every~$(t_0,\Delta_0;t_1,\Delta_1)$-tree. 
\endproclaim

The rest of this section is devoted to the proof of the above result.
Thus, suppose~$t_\sigma$, $\Delta_\sigma$ ($\sigma\in\{0,1\}$) are as
in Theorem~{\TreeUniv}, let~$T$ be a fixed
$(t_0,\Delta_0;t_1,\Delta_1)$-tree, and let~$J$ be a
$(2t_1/\Delta_0,2\Delta_0;2t_0/\Delta_1,2\Delta_1)$-expanding
bipartite graph.  
We shall show that~$J$ contains a copy of~$T$ as a subgraph.

Let~$S\subset T$ be a subtree of~$T$. 
A function~$f\colon V(S)\to V(J)$ is an {\deffont embedding\/} of~$S$
in~$J$ if~$f$ is injective, it preserves the adjacency relation, and
moreover it preserves the vertex classes, {\it
  i.e.\/}~$f(V_\sigma(T)\cap V(S))\subset V_\sigma(J)$
for~$\sigma\in\{0,1\}$. 
In what follows the indices will be reduced modulo~$2$, so that, for
instance, $V_0(J)=V_2(J)=\cdots\,$.  
Let us now suppose that an embedding~$f\colon S\to J$ is 
given, and suppose~$X\subset V_\sigma(J)$ ($\sigma\in\{0,1\}$). 
Then we let~$A_f(X)=|\Gamma_J(X)\setminus f(V(S))|$.  
Also, for~$x\in J$ we let~$D_f(x)=d_S(f^{-1}(x))$ if~$x\in f(V(S))$
and~$D_f(x)=0$ otherwise, and put~$B_f(X)=\sum_{x\in
  X}(\Delta_\sigma-D_f(x))$.  
Finally, we set~$C_f(X)=A_f(X)-B_f(X)$.

Let us say that~$X$ is {\deffont$f$-solvent\/} if~$C_f(X)\geq0$, and
{\deffont$f$-bankrupt\/} otherwise. 
If~$C_f(X)=0$, we shall say that~$X$ is {\deffont$f$-critical\/}. 
A central definition is the following. 
We shall say that~$f$ is {\deffont good\/} if every~$X\subset V(J)$
with~$X\subset V_\sigma(J)$ ($\sigma\in\{0,1\}$) is $f$-solvent 
whenever~$|X|\leq2t_{\sigma+1}/\Delta_\sigma$. 
We have now arrived at the main claim in the proof of
Theorem~{\TreeUniv}.  

\claim {\rm({\it i\/})}~If~$S\subset T$ is a subtree of~$T$
with~$|S|=1$, then 
there is a good embedding~$f\colon S\to J$ of~$S$ in~$J$. 
{\rm({\it ii\/})}~Let~$S\subset T$ be a subtree of~$T$, and
suppose~$f\colon S\to J$ is a good embedding of~$S$ in~$J$. 
If~$S\subset S'\subset T$, where~$S'$ is a tree
with~$|S'|=|S|+1$, then there is a good embedding~$g\colon S'\to J$ 
of~$S'$ in~$J$ that extends~$f$. 
\endclaim

As Theorem~{\TreeUniv} immediately follows from~({\it i\/}) and~({\it
  ii\/}) above, we proceed to prove this claim. 
Let us first consider~({\it i\/}).
Suppose~$V(S)=\{x\}\subset V_\sigma(T)$ ($\sigma\in\{0,1\}$). 
Then let~$f\colon V(S)\to V(J)$ be any function such that~$f(x)\in
V_\sigma(J)$. 
We claim that~$f$ is a good embedding. 
To check this, let~$X\subset V_\rho(J)$ ($\rho\in\{0,1\}$) be such
that~$|X|\leq2t_{\rho+1}/\Delta_\rho$.   
Let us check that~$C_f(X)\geq0$.  
If~$X=\emptyset$, then clearly~$C_f(X)=A_f(X)=B_f(X)=0$, and so we
assume that~$X\neq\emptyset$. 
Note that then~$A_f(X)=|\Gamma_J(X)\setminus\{f(x)\}|\geq
2\Delta_\rho|X|-1\geq\Delta_\rho|X|\geq B_f(X)$. 
Thus~$C_f(X)\geq0$, and~$f$ is indeed good. 
We now turn to~({\it ii\/}). 

Suppose~$f\colon S\to J$ and~$S\subset S'\subset T$ are as in the
statement of~({\it ii\/}). 
Then clearly there is a leaf~$v$ of~$S'$ such that~$V(S')\setminus
V(S)=\{v\}$. 
Let~$w\in S$ be the unique neighbour of~$v$ in~$S'$.
Suppose~$v\in V_{\sigma'}(T)$ ($\sigma'\in\{0,1\}$). 
Now let us consider all embeddings~$g\colon S'\to J$ of~$S'$ in~$J$
that extend~$f$, and let~$\G$ be the set of such extensions. 
Our claim is that~$\G$ contains a good extension.
Although strictly speaking this is not necessary, let us first check
that~$\G\neq\emptyset$ as a warm-up.  
Since~$\{f(w)\}$ is $f$-solvent, we have
that~$|\Gamma_J(f(w))\setminus f(V(S))|=A_f(\{f(w)\})\geq
B_f(\{f(w)\})=\Delta_{\sigma'+1}-d_S(w)\geq1$, which implies that
indeed~$f$ has at least one extension~$g\in\G$.
We now check that~$\G$ contains a {\it good\/} extension.

Suppose for a contradiction that every~$g\in\G$ admits a $g$-bankrupt
set~$X_g\subset V(J)$ such that~$X_g\subset V_\rho(J)$,
where~$\rho=\rho(g)\in\{0,1\}$ and $|X_g|\leq2t_{\rho+1}/\Delta_\rho$.
Since~$f$ is good, the sets~$X_g$ ($g\in\G$) are all $f$-solvent.

We now do a little simple calculation.  
For brevity, if~$P$ is a statement we set~$[P]=0$ if~$P$ is false
and~$[P]=1$ if~$P$ is true. 
Fix~$X\subset V_\rho(J)$ ($\rho\in\{0,1\}$) and let~$g\in\G$. 
Note that then~$A_g(X)=|\Gamma_J(X)\setminus
g(V(S'))|=|\Gamma_J(X)\setminus f(V(S))|-[g(v)\in\Gamma_J(X)]$.  
Moreover~$B_g(X)=\sum_{x\in
X}(\Delta_\rho-D_g(x))=B_f(X)-[f(w)\in X]-[g(v)\in X]$.  
Thus we have that
$$
C_g(X)=C_f(X)-[g(v)\in\Gamma_J(X)]+[f(w)\in X]+[g(v)\in X]. 
$$
From this, and the fact that~$X_g$ is $g$-bankrupt but $f$-solvent, 
we conclude that 
$$
\hbox{$X_g$ is $f$-critical,
      $g(v)\in\Gamma_J(X_g)\setminus X_g$,
      and~$f(w)\notin X_g$}      \slabel{Concls}
$$
for every~$g\in\G$. 
Note in particular that~$\rho(g)=\sigma'+1$ for all~$g\in\G$; that is,
we have~$X_g\subset V_{\sigma'+1}(J)$ for all~$g\in\G$. 

\proclaim Lemma {\lemmaA}. 
Suppose~$X\subset V_\rho(J)$, where~$\rho\in\{0,1\}$, is $f$-critical
and satisfies~$|X|\leq2t_{\rho+1}/\Delta_\rho$. 
Then~$|X|\leq t_{\rho+1}/\Delta_\rho$.  
\endproclaim
\proof
We have~$A_f(X)=|\Gamma_J(X)\setminus
f(V(S))|\geq2\Delta_\rho|X|-t_{\rho+1}$, and~$B_f(X)=\sum_{x\in
  X}(\Delta_\rho-D_f(x))\leq\Delta_\rho|X|$. 
Since~$A_f(X)-B_f(X)=C_f(X)=0$, the lemma follows.
\qed

We now check that~$C_f$ is a submodular function when restricted to
each of the power sets~$\cP(V_\rho(J))$ of~$V_\rho(J)$
($\rho\in\{0,1\}$).

\proclaim Lemma {\lemmaB}. 
Suppose~$X$, $Y\subset V_\rho(J)$, where~$\rho\in\{0,1\}$. 
Then
$$
C_f(X\cap Y)+C_f(X\cup Y)\leq C_f(X)+C_f(Y).  \slabel{SMod}
$$
\endproclaim
\proof
Note first that~$B_f$ is a modular function on~$\cP(V_\rho(J))$
($\rho\in\{0,1\}$).  
Now~{\eqnoSMod} follows from the observation
that~$\Gamma_J(X\cap Y)\subset\Gamma_J(X)\cap\Gamma_J(Y)$
and~$\Gamma_J(X\cup Y)=\Gamma_J(X)\cup\Gamma_J(Y)$.
\qed

An easy consequence of the above two lemmas is the following.

\proclaim Corollary {\CorC}. 
Suppose~$X$, $Y\subset V_\rho(J)$, where~$\rho\in\{0,1\}$, are
$f$-critical and moreover~$|X|$, $|Y|\leq t_{\rho+1}/\Delta_\rho$.  
Then~$X\cup Y$ is $f$-critical and~$|X\cup Y|\leq
t_{\rho+1}/\Delta_\rho$.  
\endproclaim
\proof
Since~$|X\cup Y|\leq2t_{\rho+1}/\Delta_\rho$ and~$f$ is good, the
set~$X\cup Y$ is $f$-solvent. 
Similarly~$X\cap Y$ is $f$-solvent.  
Now~{\eqnoSMod} and the fact that~$X$ and~$Y$ are $f$-critical imply
that~$X\cap Y$ and~$X\cup Y$ are $f$-critical as well.  
Lemma~{\lemmaA} now gives that~$|X\cup Y|\leq
t_{\rho+1}/\Delta_\rho$, as required.
\qed

We are now ready to finish the proof of~({\it ii\/}) of our claim.
Let~$X^*=\bigcup_{g\in \G}X_g\subset V_{\sigma'+1}(J)$. 
By Corollary~{\CorC}, we have that~$X^*$ is $f$-critical
and~$|X^*|\leq t_{\sigma'}/\Delta_{\sigma'+1}$. 
Recall that~$f(w)\notin X_g$ for any~$g\in\G$
(cf.~{\eqnoConcls}), and so~$f(w)\notin X^*$. 
Let~$X'=X^*\cup\{f(w)\}\subset V_{\sigma'+1}(J)$. 
We now claim that
$$
\Gamma_J(X')\setminus f(V(S))=\Gamma_J(X^*)\setminus f(V(S)).
\slabel{Afs} 
$$
It suffices to check that if~$y\in\Gamma_J(f(w))\setminus f(V(S))$,
then~$y\in\Gamma_J(X^*)$. 
So suppose~$y\in\Gamma_J(f(w))\setminus f(V(S))$ is
fixed. 
Then note that there is an extension~$g\in\G$ of~$f$ for
which~$g(v)=y$. 
But then by~{\eqnoConcls} we conclude
that~$y=g(v)\in\Gamma_J(X_g)\subset\Gamma_J(X^*)$.  
Thus~{\eqnoAfs} does indeed hold, and we have~$A_f(X')=A_f(X^*)$.  
Now note that~$B_f(X')=B_f(X^*)+(\Delta_{\sigma'+1}-d_S(w))>B_f(X^*)$.  
Thus~$C_f(X')<C_f(X^*)=0$. 
However, $|X'|=|X^*|+1\leq
t_{\sigma'}/\Delta_{\sigma'+1}+1\leq2t_{\sigma'}/\Delta_{\sigma'+1}$,
and hence, as~$f$ is good, we have that~$C_f(X')\geq0$. 
This contradiction completes the proof of Theorem~{\TreeUniv}.
%
% sec3
%
\beginsection 3. Bipartite graphs with uniformly distributed edges 

Let integers~$n_0$, $n_1\geq1$ and~$r_0$, $r_1\geq1$ be such
that~$n_0r_0=n_1r_1$. 
Set~$r=\max\{r_0,r_1\}$, and let~$p=(r_0/n_1)\log
r=(r_1/n_0)\log r$. 
We shall assume throughout that~$r\geq3$ and~$p\leq1$.
Consider the space~$\G(n_0,n_1;p)$ of random bipartite
graphs~$G=G_{n_0,n_1,p}$ with vertex classes~$V_0(G)$ and~$V_1(G)$
satisfying~$|V_\sigma(G)|=n_\sigma$ ($\sigma\in\{0,1\}$), and where
each edge is independently present with probability~$p$. 
Our aim in this section is to show the following technical lemma,
which we shall do with the aid of the random graphs~$G_{n_0,n_1,p}$. 
If~$G$ is a graph and~$U$, $W\subset V(G)$, we 
let~$e_G(U,W)$ denote the number of edges that have one endvertex
in~$U$ and the other in~$W$. 

\proclaim Lemma~{\TechLemma}. 
There is an absolute constant~$r^*\geq1$ for which the following
holds.  
Let~$n_0$, $n_1$, $r_0$, $r_1\geq1$ be integers
with~$n_0r_0=n_1r_1$, and set~$p=(r_0/n_1)\log r=(r_1/n_0)\log
r$ where~$r=\max\{r_0,r_1\}$. 
Suppose~$0<\alpha\leq1$ satisfies~$\alpha r_0$, $\alpha r_1\geq1$.  
Then if~$r\geq r^*$ there is a bipartite
graph~$G=G^{n_0,n_1}$ such that {\rm({\it i\/})}~$1/2\leq
e(G)/n_0r_0\log r\leq2$, and {\rm({\it ii\/})}~if~$\sigma\in\{0,1\}$,
for any~$U\subset V_\sigma(G)$, $W\subset V_{\sigma+1}(G)$ with~$1\leq
u=|U|\leq u_\sigma=\lfloor n_{\sigma+1}/\e r_\sigma\rfloor=\lfloor
n_\sigma/\e r_{\sigma+1}\rfloor$ and~$w=|W|=\lfloor\alpha r_\sigma
u\rfloor$, we have 
$$
e(U,W)=e_G(U,W)<puw+12\e(r_\sigma uw)^{1/2}\log r. \slabel{Cond}
$$
\endproclaim
\proof
Note that if~$p\geq1$, we may take for~$G$ a complete bipartite graph 
with vertex classes of order~$n_0$ and~$n_1$. 
Thus we assume that~$p<1$.  
We shall show that then, provided~$r$ is large enough, the probability 
that~$G=G_p=G_{n_0,n_1,p}\in\G(n_0,n_1;p)$ satisfies~({\it i\/})
and~({\it ii\/}) is positive. 
For~$\sigma\in\{0,1\}$, let~$Q_\sigma$ be the property
given in assertion~({\it ii\/}). 
We shall in fact show that, as~$r\to\infty$,
we have ({\it iii\/})~$\P(Q_\sigma)=1-o(1)$ ($\sigma\in\{0,1\}$) and
({\it iv\/})~$\P(1/2\leq e(G)/r_0n_0\log r\leq2)=1-o(1)$.

Let us check~({\it iii\/}) first, and notice that by symmetry we may
assume~$\sigma=0$. 
Let~$1\leq u\leq u_0$ and $w=w(u)=\lfloor\alpha r_0
u\rfloor$. 
Set~$A=12\e$, $\mu=puw$, and~$b=A(r_0uw)^{1/2}\log r$.
Let~$U\subset V_0(G)$ and~$W\subset V_1(G)$ be such that~$|U|=u$
and~$|W|=w$. 
Let~$P_u=\P(e(U,W)\geq\mu+b)$, and set~$E_0=\sum_{1\leq u\leq
  u_0}{n_0\choose u}{n_1\choose w}P_u$. 
Our aim is to show that~$E_0=o(1)$ as~$r\to\infty$. 
Let
$$
\eta={b\over\mu}={A(r_0uw)^{1/2}\log r\over(r_0/n_1)uw\log r}
  =An_1(r_0uw)^{-1/2}.  \slabel{eta}
$$
We estimate~$E_0=\sum_u{n_0\choose u}{n_1\choose w}P_u$ by breaking
the sum into two parts. 
Let~$E_0^{(1)}=\sum^*{n_0\choose u}{n_1\choose w}P_u$,
where~$\sum^*$ denotes sum over all~$1\leq u\leq u_0$
with~$\eta\leq\e^2$, and let~$E_0^{(2)}=E_0-E_0^{(1)}$. 
Note that below we may assume that~$r$ is large enough for our
inequalities to hold.  

\assertion(1) We have~$E_0^{(1)}=o(1)$ as~$r\to\infty$.
\endassertion
\proofofassertion
Here we assume throughout that~$\eta\leq\e^2$.  
We start by claiming
that~$P_u=\P(e(U,W)\geq\mu+b)\leq\exp\big\{-\big(A^2/3\e^4\big)n_1\log  
r\big\}$. 
To check this claim, let us first consider the case in
which~$\eta\leq1$. 
Note that from~{\eqnoeta} we have
that~$\eta^2\mu=A^2n_1\log r$. 
Then Hoeffding's inequality~{\refHoeff} (see also~{\refMcD}) gives 
that~$P_u\leq\exp\big\{-\big(A^2/3\big)n_1\log r\big\}$, and the claim
follows in this case. 
Now consider the case~$1\leq\eta\leq\e^2$.
Here~$P_u\leq\P(e(U,W)\geq2\mu)\leq\exp\{-\mu/3\}$, again by
Hoeffding's inequality. 
Note that~$b/\mu=\eta\leq\e^2$ gives that~$\mu\geq
b/\e^2=(A/\e^2)(r_0uw)^{1/2}\log r$.  
Also, we have~$An_1(r_0uw)^{-1/2}=\eta\leq\e^2$, and
therefore~$\mu\geq(A^2/\e^4)n_1\log r$. 
Thus our claimed upper bound for~$P_u$ follows.

We now estimate~$E_0^{(1)}$. 
If~$n_0\leq n_1$ this is very quick: note that 
$$
E_0^{(1)}=\sum\nolimits^*{n_0\choose u}{n_1\choose w}P_u
   \leq2^{n_0+n_1}\exp\left\{-{A^2\over3\e^4}n_1\log r\right\}
   \leq\big(4r^{-6}\big)^{n_1}=o(1)
$$
as~$r\to\infty$. 
Thus let us assume that~$n_0>n_1$. 
Then
$$
\eqalignno{
E_0^{(1)}&\leq2^{n_1}\sum\nolimits^*{n_0\choose u}P_u 
   \leq3\times2^{n_1}
     \exp\left\{-{A^2\over3\e^4}n_1\log r\right\}
               \(\e n_0\over u_0\)^{u_0}\cr
&\qquad\leq3\times2^{n_1}\big(\e^2r_1\big)^{n_1/\e r_0}
      \exp\left\{-{A^2\over3\e^4}n_1\log r\right\} \cr
&\qquad\qquad\qquad\leq3\times2^{n_1}
     \exp\left\{{2n_1\over\e r_0}+{n_1\over\e r_0}\log r
        -{A^2\over3\e^4}n_1\log r\right\}, \cr
}
$$
which tends to~$0$ as~$r\to\infty$. 
\endproofofassertion
\assertion(2)We have~$E_0^{(2)}=o(1)$ as~$r\to\infty$. 
\endassertion
\proofofassertion
We now assume that~$\eta\geq\e^2$.  
Let~$v$ be such that~$b=\e v\mu/\log v$.
Then~$\e v/\log v=b/\mu=\eta\geq\e^2$, and hence we may
suppose~$v\geq\e$. 
Also, we have~$\e v\mu/\log v=b\geq1\geq\e/v$, and so~$v^2\mu\geq\log 
v$. 
Thus~$P_u\leq\P(e(U,W)\geq b)\leq\exp\{-v\mu\}$ (see Theorem~7({\it
  ii\/}) in Chapter~I of~{\refBBf}).  
Now, we have~$v\mu=(b/\e)\log
v\geq12(r_0uw)^{1/2}(\log r)(\log v)\geq12(r_0uw)^{1/2}(\log r)$. 
Thus~$v\geq12(r_0uw)^{-1/2}n_1$, and hence
$$
P_u\leq\exp\{-v\mu\}
    \leq\((r_0uw)^{1/2}\over12n_1\)^{12(r_0uw)^{1/2}\log r}. 
     \slabel{A}
$$
Note that if~$w\leq1$ then~$u\leq1$, and hence~{\eqnoCond} holds
trivially; that is, we have~$P_u=0$ in this case.
Thus we assume~$\alpha r_0 u\geq\lfloor\alpha r_0 u\rfloor=w\geq2$.     
Hence~$w\geq\alpha r_0 u/2$, and we have from~{\eqnoA} that
$$
P_u\leq\(\alpha ^{1/2}r_0u\over12n_1\)^{6\alpha r_0u\log r}. 
$$
Thus~$E_0^{(2)}=\sum^\dagger{n_0\choose u}{n_1\choose w}P_u$,
where~$\sum^\dagger$ indicates sum over all~$2\leq u\leq u_0$
with~$\eta\geq\e^2$, is at most  
$$
\eqalign{
\sum\nolimits^\dagger
  \(\e n_0\over u\)^u\(\e n_1\over\alpha r_0u\)^{\alpha r_0u}P_u
  &\leq\sum_{u=2}^{u_0}\(\e n_0\over u\)^u
    \left\{{\e n_1\over\alpha r_0u}
         \(ur_0\over n_1\)^{6\log r}\right\}^{\alpha r_0u}\cr
  &\leq\sum_{u=2}^{u_0}\(\e n_0\over u\)^u
          \(1\over\alpha \)^{\alpha r_0u}
              \(ur_0\over n_1\)^{4\alpha r_0u\log r}\cr
  &\leq\sum_{u=2}^{u_0}\(\e r_1\(1\over\alpha \)^{\alpha r_0}
                   \(ur_0\over n_1\)^{3\alpha r_0\log r}\)^u,\cr
}
$$
which is at most~$\sum_{2\leq u\leq u_0}\e^u\{\alpha r^2\}^{-\alpha 
r_0u}\leq\sum_{u\geq2}(\e/r)^u=o(1)$ as~$r\to\infty$.   
\endproofofassertion

Thus we have shown that~$E_0=E_0^{(1)}+E_0^{(2)}=o(1)$
as~$r\to\infty$, and hence that~({\it iii\/}) above does indeed hold.   
To see~({\it iv\/}), it suffices to note that~$e(G)$ has binomial
distribution~$\Bi(n_0n_1,p)$ with parameters~$n_0n_1$ and~$p$ and
that~$\E(e(G))=pn_0n_1=n_0r_0\log r\to\infty$ as~$r\to\infty$.
\qed

When~$n_0=n_1$ in Lemma~{\TechLemma}, we may require a more
restrictive condition on~$G=G^{n,n}$, as shows Lemma~{\TechLemmaB}
below.  
One may prove this lemma by suitably altering the proof of
Lemma~{\TechLemma} and hence we omit its proof.

\proclaim Lemma {\TechLemmaB}. 
There is an absolute constant~$r^*\geq1$ for which the following
holds.  
Let~$r^*\leq r\leq n$, set~$p=r/n$, and suppose~$0<\alpha\leq1$
satisfies~$\alpha r\geq1$.
Then there is a bipartite graph~$G=G^{n,n}$ such that {\rm({\it
i\/})}~$1/2\leq e(G)/nr\leq2$, and {\rm({\it
ii\/})}~if~$\sigma\in\{0,1\}$, for any~$U\subset V_\sigma(G)$,
$W\subset V_{\sigma+1}(G)$ with~$1\leq u=|U|\leq n/2r$
and~$w=|W|=\lfloor\alpha ru\rfloor$, we
have~$e_G(U,W)<puw+12\e(ruw)^{1/2}$. 
\endproclaimsquare
%
% sec4 and sec5
%
\beginsection 4. The main results

Let~$H$ be a bipartite graph with bipartition~$V(H)=V_0(H)\cup
V_1(H)$, and suppose~$V_0(H)$, $V_1(H)\neq\emptyset$. 
Let~$\dbar_\sigma(H)=|V_\sigma(H)|^{-1}\sum\{d_H(v)\colon v\in
V_\sigma(H)\}$ be the 
average degree of the vertices in~$V_\sigma(H)$ ($\sigma\in\{0,1\}$).   
The following simple but useful lemma was observed by
Beck~{\refBeckB}.  
We include Beck's proof of this lemma for completeness.

\proclaim Lemma {\BeckLemma}. 
Let~$H$ be as above. 
Then there is a non-empty induced subgraph~$J\subset H$ of~$H$ such
that {\rm(*)}~for any~$U\subset V_\sigma(J)=V_\sigma(H)\cap V(J)$
$(\sigma\in\{0,1\})$, we
have~$e_J(U,V(J))\geq(1/2)\dbar_\sigma(H)|U|$. 
\endproclaim
\proof
We define a sequence~$H=H_0\superset H_1\superset\cdots$ of induced
subgraphs of~$H$ as follows.  
Let~$H_0=H$, and suppose~$H_0\superset\cdots\superset
H_{i-1}$ ($i\geq1$) have been defined. 
If~$|H_{i-1}|=0$, or else~$|H_{i-1}|>0$ 
and condition~(*) in our lemma holds, we terminate the sequence.
Suppose~$|H_{i-1}|>0$ but~(*) fails. 
Then let~$U\subset V(H_{i-1})$ be such
that~$U\subset V_\sigma(H_{i-1})$ for some~$\sigma\in\{0,1\}$, and
moreover~$e_{H_{i-1}}(U,V(H_{i-1}))<(1/2)\dbar_\sigma(H)|U|$. 
We now let~$H_i=H_{i-1}-U$. 
This defines a sequence~$H=H_0\superset\cdots\superset
H_t$ of induced subgraphs of~$H$. 
If~$J=H_t$ is as required, we are done. 
Thus suppose~$|H_t|=0$. 
But then
$$
e(H)=\sum_{1\leq i\leq t}\big(e(H_{i-1})-e(H_i)\big)
   <{1\over2}\dbar_0(H)|V_\sigma(H)|
     +{1\over2}\dbar_1(H)|V_\sigma(H)|=e(H),
$$
which is a contradiction, and hence we necessarily have~$|H_t|>0$.
\qed

We may now prove our first main result. 

\proclaim Theorem {\MainResA}. 
Let~$0<\gamma\leq1$ be given. 
Then there is a constant~$c_\gamma>0$ depending only on~$\gamma$ for
which the following holds.  
For all integers~$1\leq\Delta_0\leq t_1$ and~$1\leq\Delta_1\leq t_0$, 
there is a bipartite graph~$G$ such that {\rm({\it i\/})}~$e(G)\leq
c_\gamma(\Delta_0t_0+\Delta_1t_1)\log\Delta$,
where~$\Delta=\max\{\Delta_0,\Delta_1\}$, and {\rm({\it
ii\/})}~$G\darrows\gamma T$ for any
$(t_0,\Delta_0,t_1,\Delta_1)$-tree~$T$.  
\endproclaim
\proof
Let~$\gamma$, $t_\sigma$, $\Delta_\sigma$ ($\sigma\in\{0,1\}$) be as
above. 
In proving our result, we may assume that~$\Delta\geq\e^2r^*$,
where~$r^*$ is as given in Lemma~{\TechLemma}. 
Moreover, we may further assume that~$\Delta_0t_0\geq\Delta_1t_1$.  
We now start the proof proper.

Let~$0<\alpha=\alpha(\gamma)\leq\min\{\e\gamma/4,4/\e^2\}$ be the
largest real number such that
$(1/12\e)^2(\gamma/4-\alpha/\e)^2\geq\alpha$. 
For~$\sigma\in\{0,1\}$, let~$r_\sigma$ be the smallest integer power
of~$2$ such that~$\alpha r_\sigma\geq2\Delta_\sigma$.
Clearly~$r_\sigma\leq(4/\alpha)\Delta_\sigma$ ($\sigma\in\{0,1\}$).
Now let~$n_0$ be the smallest power of~$2$ such that~$n_0\geq2\e
t_0r_1/\Delta_1$. 
Then we have~$n_0\leq(16\e/\alpha)t_0$. 
Finally, let~$n_1=r_0n_0/r_1$. 
Then note that~$n_1/\e r_0\geq n_0/\e
r_1\geq2t_0/\Delta_1\geq2t_1/\Delta_0$.   
Now let~$G=G^{n_0,n_1}$ be the bipartite graph whose existence is
guaranteed in Lemma~{\TechLemma}.  
Then
$$
e(G)\leq2n_0r_0\log r
  \leq2\(16\e t_0\over\alpha\)\(4\Delta_0\over\alpha\)
         \log\(4\Delta\over\alpha\)
      \leq c_\gamma'(t_0\Delta_0+t_1\Delta_1)\log\Delta,
$$
where~$c_\gamma'=128\e\alpha^{-2}\log(4/\alpha)$,
since~$\log(4\Delta/\alpha)\leq(\log(4/\alpha))\log\Delta$
as~$\alpha\leq4\e^{-2}$ and~$\Delta\geq\e^2$.  
Thus~({\it i\/}) in our result
holds for~$G$ if~$c_\gamma\geq c_\gamma'$.
We now check~({\it ii\/}). 
Thus let~$H\subset G$ be a fixed subgraph of~$G$ with~$e(H)\geq\gamma 
e(G)$.  
Let~$J\subset H$ be the subgraph of~$H$ given by Lemma~{\BeckLemma}.   
We claim that then the graph $J$ is 
$(2t_1/\Delta_0,2\Delta_0;2t_0/\Delta_1,2\Delta_1)$-expanding.

Suppose for a contradiction that~$U\subset V_\sigma(J)$ is such
that~$u=|U|\leq2t_{\sigma+1}/\Delta_\sigma$
and~$|\Gamma_J(U)|<2\Delta_\sigma|U|$, where~$\sigma\in\{0,1\}$. 
Then, let~$W\subset V_{\sigma+1}(J)$ be such that~$w=|W|=\lfloor\alpha
r_\sigma u\rfloor$ and~$\Gamma_J(U)\subset W$.  
Now observe that
$$
\eqalign{
{\gamma\over4}r_\sigma(\log r)u
  \leq{\gamma\over2}\dbar_\sigma(G)u\leq{1\over2}\dbar_\sigma(H)u 
      \leq e_J(U,V(J))\leq e_G(U,W)\qquad&\cr
 \qquad<puw+12\e(r_\sigma uw)^{1/2}\log r
   \leq{\alpha\over\e}r_\sigma(\log r)u
        +12\e(r_\sigma uw)^{1/2}\log r.&\cr 
}
$$
Thus~$(\gamma/4-\alpha/\e)r_\sigma(\log r)u<12\e(r_\sigma
uw)^{1/2}\log r$, and hence we have~$\alpha r_\sigma 
u\leq(1/12\e)^2(\gamma/4-\alpha/\e)^2r_\sigma u<w=\lfloor\alpha
r_\sigma u\rfloor$, which is a contradiction. 
Therefore we conclude that indeed~$J$ is
$(2t_1/\Delta_0,2\Delta_0;2t_0/\Delta_1,2\Delta_1)$-expanding.  
Now~({\it ii\/}) above follows from Theorem~{\TreeUniv}.
\qed

Our second main result is as follows. 

\proclaim Theorem {\MainResB}. 
Let~$0<\gamma\leq1$ be given. 
Then there is a constant~$c_\gamma>0$ depending only on~$\gamma$ for
which the following holds.  
For any~$1\leq\Delta<t$, there is a bipartite graph~$G$
such that {\rm({\it i\/})}~$e(G)\leq c_\gamma\Delta t$, and {\rm({\it 
ii\/})}~$G\darrows\gamma T$ for any tree~$T$ of order~$|T|\leq t$ and
maximal degree~$\Delta(T)\leq\Delta$.
\endproclaim
\proof
Let~$\gamma$, $\Delta$, $t$ be as in the statement of our result. 
We may assume that~$\Delta\geq r^*$, where~$r^*$ is as in
Lemma~{\TechLemmaB}. 
Let~$0<\alpha=\alpha(\gamma)\leq\gamma/2$ be the largest real such
that~$(1/12\e)^2(\gamma/4-\alpha/2)^2\geq\alpha$. 
Now let~$r=\lceil2\Delta/\alpha\rceil\leq4\Delta/\alpha$,
and~$n=\lceil4tr/\Delta\rceil\leq32t/\alpha$. 
Note that then~$r^*\leq r\leq n$, $0<\alpha\leq1$, and let~$G=G^{n,n}$ 
be the corresponding bipartite graph given by Lemma~{\TechLemmaB}. 
Then~$e(G)\leq2rn\leq2(4\Delta/\alpha)(32t/\alpha)
\leq256\alpha^{-2}\Delta t$. 
We now check that~$G\to_\gamma T$ for any tree~$T$ with~$|T|\leq t$
and~$\Delta(T)\leq\Delta$. 
Let~$H\subset G$ be a subgraph of~$G$ with~$e(H)\geq\gamma e(G)$. 
Let~$J\subset H$ be the subgraph of~$H$ given by Lemma~{\BeckLemma}.  
It now suffices to check that~$J$ is a
$(2t/\Delta,2\Delta;2t/\Delta,2\Delta)$-expanding bipartite graph.  

Suppose for a contradiction that~$U\subset V_\sigma(J)$ is such
that~$|\Gamma_J(U)|<2\Delta|U|$ although~$u=|U|\leq2t/\Delta$,
where~$\sigma\in\{0,1\}$. 
Then, let~$W\subset V_{\sigma+1}(J)$ be such 
that~$w=|W|=\lfloor\alpha ru\rfloor$ and~$\Gamma_J(U)\subset W$. 
Now observe that  
$$
\eqalign{
{\gamma\over4}ru
   \leq{\gamma\over2}\dbar_\sigma(G)u\leq{1\over2}\dbar_\sigma(H)u
      \leq e_J(U,V(J))\leq e_G(U,W)\qquad\qquad&\cr
 \qquad<puw+12\e(ruw)^{1/2}
     \leq{\alpha\over2}ru+12\e(ruw)^{1/2}.&\cr 
}
$$
Thus~$\alpha ru\leq(1/12\e)^2(\gamma/4-\alpha/2)^2ru<w=\lfloor\alpha
ru\rfloor$, which is a contradiction.
\qed

An immediate corollary to Theorems~{\MainResA} and~{\MainResB} is the upper
bound for the size-Ramsey number of trees given in Corollary~{\CorSizeR}
below. 
The lower bound in this corollary is due to Beck~{\refBeckB}, and its
very short proof is included for convenience.

\proclaim Corollary {\CorSizeR}. 
For any~$r\geq2$, there is a constant~$c_r$ depending only on~$r$ such
that 
$$
\beta(T)/4\leq\sizeR(T,r)\leq c_r\min\{\beta(T)\log\Delta(T),|T|\Delta(T)\} 
$$
for all trees~$T$. 
\endproclaim
\proof
Let an integer~$r\geq2$ and a tree~$T$ be fixed. 
Let~$T$ have bipartition~$V(T)=V_0(T)\cup V_1(T)$, and
let~$t_\sigma=|V_\sigma(T)|$, $\Delta_\sigma=\Delta_\sigma(T)$
($\sigma\in\{0,1\}$).  
We may assume that~$t_0\Delta_0\geq t_1\Delta_1$. 
Let us prove that~$\sizeR(T,2)\geq\beta(T)/4$.  
Suppose~$G\to(T)_2$. 
Let~$U=\{v\in G\colon d_G(v)\geq\Delta_0\}$ and set~$W=V(G)\setminus
U$.  
Colour the edges of~$G$ between~$U$ and~$W$ red, and the rest of the
edges of~$G$ blue.
Suppose~$T'\subset G$ is a monochromatic copy of~$T$ in~$G$, and
let~$\phi\colon T\to T'$ be an isomorphism. 
Let~$v_0\in V_0(T)$ have degree~$d_T(v)=\Delta_0$. 
Clearly~$\phi(v_0)\in U$, and hence regardless of
the colour of~$T'$, we have~$\phi(V_0(T))\subset U$.
Thus~$e(G)\geq|U|\Delta_0/2\geq|V_0(T)|\Delta_0/2=
t_0\Delta_0/2\geq\beta(T)/4$. 
The upper bound for~$\sizeR(T,r)$ follows immediately from
Theorems~{\MainResA} and~{\MainResB}. 
\qed

\beginsection 5. Concluding remarks

The existence of the graph~$G$ in Theorem~{\MainResB} is proved by
non-constructive means. 
For some values of~$\gamma$, $\Delta$, and~$t$
we may however take for~$G$ a suitable Ramanujan graph~$X=X^{p,q}$.
More precisely, there is an absolute constant~$\epsilon>0$ with the
following property. 
For any given~$0<\gamma\leq1$, there exist
constants~$c_\gamma>0$, $\Delta_\gamma$, 
$t_\gamma\geq1$ depending only on~$\gamma$ such that, for any
integers~$1\leq\Delta<t$ with~$\Delta\geq\Delta_\gamma$, $t\geq
t_\gamma$, and~$\Delta\leq t^\epsilon$, there are primes~$p$ and~$q$
such that a bipartite Ramanujan graph~$X=X^{p,q}$ constructed by 
Lubotzky, Phillips, and Sarnak~{\refLPS} is such that ({\it
i\/})~$e(X)\leq c_\gamma\Delta t$, and ({\it ii\/})~$X\darrows\gamma  
T$ for any tree~$T$ of order~$|T|\leq t$ and maximal
degree~$\Delta(T)\leq\Delta$. 
The only extra work involved in proving the statement above has to do
with the existence of the primes~$p$ and~$q$. 
We refer the reader to Section~4 of~{\refHKb}, where a
similar number-theoretic problem is treated. 
The key result there is a beautiful theorem of Bombieri~{\refBomb}
(see also~Davenport~{\refDave}, \S28) on the distribution of primes in  
arithmetic progressions.  
With this result in hand, our task there is
quite straightforward, and in fact the same method applies here,
proving the above assertion. 
Let us also remark that the techniques
presented in this note also show that the incidence graphs of certain
projective geometries are explicit examples that prove
Theorem~{\MainResB} for~$\Delta$ and~$t$ with~$\Delta$
about~$t^{1-1/d}$ for some integer~$d\geq2$. 
(See Theorem~2.3 in Alon~{\refAlon}.)

Finally, we should like to mention that Professor Noga Alon~{\refApc}
has kindly pointed out to us that one may improve the observations
above as follows. 
One of the methods that is given for the
construction of almost $k$-wise independent random variables in Alon,
Goldreich, H\aa stad, and Peralta~{\refAGHP}, namely, Construction~3,
can be suitably modified to give an elementary construction of an
$r$-regular $n$-vertex graph whose second largest eigenvalue in
absolute value~$\mu_1$ is such that~$|\mu_1|\leq ur^{1/2}$,
where~$n=2^{uk}$ and~$r=2^{2k}$, and~$u$ and~$k$ are any fixed
integers with~$u\geq3$ and~$k\geq1$.  
Here one considers a suitable Cayley graph of a certain Abelian group, 
and uses the result given in Problem~11.8 of Lov\'asz~{\refLo} (see 
Section~3.2 of Alon and Roichman~{\refAR}). 
These graphs, the Ramanujan graphs of Lubotzky, Phillips, and Sarnak
and, as pointed out by Professor Alon, their powers may be used to
prove appropriate variants of Lemma~{\TechLemmaB} constructively, thus
allowing one to give a constructive proof of Theorem~{\MainResB} for a
wide range of values of~$\gamma$, $\Delta$, and~$t$.\par 
%
% \shipoutreferences
%
\firstgofalse\refno=0\beginreferences\parindent=2em
\paper[Alon] \Al
            Eigenvalues, geometric expanders, sorting in rounds, %
            and Ramsey theory
            \Comb\vol6
            207--219, 1986
\dammit[Apc] \Al
            Personal communication, August~1993
\paper[AC]  \Al, \Chung
            Explicit construction of linear sized tolerant networks 
            \DM\vol72
            15--19, 1988
\paper[AGHP] \Al, Goldreich, O., H\aa stad, J., Peralta, R.
            Simple constructions of almost $k$-wise %
            independent random variables
            \RSA\vol3
            289--304, 1992
\dammit[AR] \Al, Roichman, Y.
            Random Cayley graphs and expanders, to appear
\paper[Beck] \Be
            On size Ramsey number of paths, trees, and circuits~I
            \JGT\vol7
            115--129, 1983
\dammit[BeckB] \Be 
            On size Ramsey number of paths, trees, and circuits~II, %
            in {\it Mathematics of Ramsey Theory\/}  (\Ne, \Ro, eds), %
            Algorithms and Combinatorics~5, Springer-Verlag, %
            Berlin~1990, pp.~34--45
\book[BBf]  \BB
            Random Graphs
            Academic Press, London, 1985, ${\it xvi}+447$pp
\paper[Bomb] Bombieri, E.
            On the large sieve
            Mathematika\vol12
            201--225, 1965
\book[Dave] Davenport, H.
            Multiplicative Number Theory,~{\rm Second edition, %
            Graduate Texts in Mathematics~74}
            Springer--Verlag, New York~1980, ${\it xiv}+177$pp
\paper[FP]  Friedman, J., Pippenger, N.
            Expanding graphs contain all small trees
            \Comb\vol7
            71--76, 1987
\dammit[HKb] Haxell, P.E., Kohayakawa, Y.
            On an anti-Ramsey property of Ramanujan graphs, to appear
\paper[Hoeff] Hoeffding, W. 
            Probability inequalities for sums of bounded random %
            variables  
            Jour. Amer. Statistical Assoc.\vol58 
            13--30, 1963
\paper[Ke]  Ke, X. 
            The size Ramsey number of trees with bounded degree
            \RSA\vol4
            85--97, 1993
\dammit[Lo] \Lo
            {\it Combinatorial Problems and Exercises\/}, %
            North Holland, Amsterdam~1979
\paper[LPS] Lubotzky, A., Phillips, R., Sarnak, P.
            Ramanujan graphs
            \Comb\vol8
            261--277, 1988
\dammit[McD] McDiarmid, C.J.H. 
            On the method of bounded differences, in {\it Surveys in %
            Combinatorics~1989\/} (Siemons, J., ed.), London %
            Mathematical Society Lecture Notes Series~141, Cambridge %
            University Press, Cambridge~1989, pp.~148--188
\endreferences
\bye
% Local Variables: 
% mode: tex
% TeX-master: t
% End: 
