%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Plain TeX-file for `On an Anti-Ramsey Property of Ramanujan Graphs'
%
% by P.E. Haxell and Y. Kohayakawa 
%
% (to appear in RSA)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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
\let\deffont=\it
%\font\deffont=cmssi10
% 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\LSU{\noindent Department of Mathematics, \hfill\break
         Louisiana State University, Baton Rouge, LA 70803, USA}
\def\IMEUSP{\noindent 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\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.tex
%
\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\RoTu
{\statementlabel}\newstatemno
\edef\prob
{\statementlabel}\newstatemno
\edef\Ram
{\statementlabel}\newstatemno
\edef\Beck
{\statementlabel}\newstatemno
\edef\MainLemma
{\statementlabel}\newstatemno
\edef\splitting
{\statementlabel}\newstatemno
\edef\MainRes
{\statementlabel}\newstatemno
\edef\Bomb
{\statementlabel}\newstatemno
\edef\primelemma
{\statementlabel}\newstatemno
\edef\pqs
{\statementlabel}\newstatemno
\edef\fixedell
{\statementlabel}\newstatemno
\edef\GenA
{\statementlabel}\newstatemno
\edef\GenB
{\statementlabel}\newstatemno
\edef\decser
{\statementlabel}\newstatemno
\edef\cues
{\statementlabel}\newstatemno
\edef\rbdd
{\statementlabel}\newstatemno
%
% macros.tex
%
\xdef\Section{\S}
\let\epsilon=\varepsilon
\let\phi=\varphi
\def\G{{\cal G}}
\def\bS{{\bar S}}
\def\S#1{S^{(#1)}}
\def\mod{\mathop{\rm mod}}
\def\Ave{\mathop{\rm Ave}}
\def\ex{\mathop{\rm ex}}
\def\li{\mathop{\rm li}}
\def\mcarrow{{\displaystyle
  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\sevenrm mc}}
                                          _{\hbox{\sevenrm p}}}}}
\def\rbddarrow{{\displaystyle
  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\sevenrm mc}}_r}}}
\def\F{{\cal F}}
\def\cP{{\cal P}}
%
% \scanreferences
%
\firstgotrue\refno=0\beginreferences
\paper[Alon] \Al
            Eigenvalues and expanders
            \Comb\vol6
            83--96, 1986
\paper[AC]  \Al, \Chung
            Explicit construction of linear sized tolerant networks 
            \DM\vol72
            15--19, 1988
\paper[AMb] \Al, Milman, V.D.
            $\lambda_1$, isoperimetric inequalities for graphs %
            and superconcentrators
            \JCTB\vol38
            73--88, 1985
\book[AS]   \Al, \Sp
            The Probabilistic Method
            John Wiley and Sons, Inc., New York~1992, ${\it xiii}+254$pp
\paper[Ba]  Babai, L.
            An anti-Ramsey theorem
            \GC\vol1
            23--28, 1985
\paper[Beck] Beck, J.
            On size Ramsey number of paths, trees, and circuits~I
            \JGT\vol7
            115--129, 1983
\paper[BiBo] Biggs, N.L., Boshier, A.G. 
            Note on the girth of Ramanujan graphs
            \JCTB\vol49
            190--194, 1990
\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[E]   \Er
            Some old and new problems in various branches %
            of combinatorics 
            Cong. Numerantium\vol23
            19--37, 1979
\paper[ERcan]  \Er, Rado, R.
            A combinatorial theorem
            \JLMS\vol25
            249--255, 1950
\paper[FP]  Friedman, J., Pippenger, N.
            Expanding graphs contain all small trees
            \Comb\vol7
            71--76, 1987
\dammit[FrieR] Frieze, A., Reed, B.
            Polychromatic Hamilton cycles, to appear
\paper[HTho] Hahn, G., Thomassen, C.
            Path and cycle sub-Ramsey numbers and %
            an edge-colouring conjecture
            \DM\vol62
            29--33, 1986
\dammit[HPhD] Haxell, P.E.
            {\it Extremal and Ramsey Type Results for Graphs %
            and Hypergraphs\/}, PhD thesis, University of Cambridge, %
            March~1993
\dammit[Ko] Kohayakawa, Y.
            A version of Szemer\'edi's regularity lemma for %
            sparse pseudo-random graphs, manuscript
\dammit[Lef] Lefmann, H.
            On an anti-Ramsey type result, %
            Pre-print~91--023, Universit\"at Bielefeld, 1991
\paper[LPS] Lubotzky, A., Phillips, R., Sarnak, P.
            Ramanujan graphs
            \Comb\vol8
            261--277, 1988
\dammit[Marg] Margulis, G.A.
            Explicit group-theoretical constructions of combinatorial %
            schemes and their application to the design of expanders and %
            superconcentrators, {\it Problemy Peredachi %
            Informatsii\/}~{\bf24} (1988), 51--60 (in Russian), %
            English translation in {\it Problems of Information %
            Transmission\/}~{\bf24} (1988), 39--46 
\dammit[NR] \Ne, \Ro
            Partite construction and Ramsey space systems, in {\it
            Mathematics of Ramsey Theory\/}, Algorithms and %
            Combinatorics~5 (\Ne, \Ro, eds), Springer-Verlag, %
            Berlin~1990, pp.~98--112
\paper[PV]  Pr\"omel, H.J., Voigt, B.
            Canonizing Ramsey theorems for finite graphs and %
            hypergraphs
            \DM\vol54
            49--59, 1985 
\paper[RoTu] \Ro, \Tu
            Rainbow subgraphs in properly edge-coloured graphs
            \RSA\vol3
            175--182, 1992
\dammit[Sz] \Sz
            Regular partitions of graphs, %
            in {\it Probl\`emes en Combinatoire et Th\'eorie des Graphes\/}, %
            Proc. Colloque Inter. CNRS %
            (Bermond, J.-C., Fournier, J.-C., Las Vergnas, M., %
            Sotteau, D., eds), CNRS, Paris~1978, pp.~399--401
\endreferences
%
% fstpg
%
\title{On an Anti-Ramsey Property of Ramanujan Graphs}

\author{P.E.~Haxell${}^1$ and Y.~Kohayakawa${}^{1,2}$}
\address
${}^1$\DPMMS\medskip
\noindent${}^2$\IMEUSP
\endaddress
\abstract
If~$G$ and~$H$ are graphs, we write~$G\to H$ (respectively, $G\to
T\!H$) if for any proper edge-colouring~$\gamma$ of~$G$ there is a
subgraph~$H'\subset G$ of~$G$ isomorphic to~$H$ (respectively, isomorphic to a
subdivision of~$H$) such that~$\gamma$ is injective on~$E(H')$.  Let us
write~$C^\ell$ for the cycle of length~$\ell$. Spencer (cf.~Erd\H os~{\refE})
asked whether for any~$g\geq3$ there is a graph~$G=G_g$ such that ({\it
i\/})~$G$ has girth~$g(G)$ at least~$g$, and ({\it ii\/})~$G\to TC^3$.
Recently, R\"odl and Tuza~{\refRoTu} answered this question in the affirmative
by proving, using non-constructive methods, a result that implies that for
any~$t\geq1$ there is a graph~$G=G_t$ of girth~$t+2$ such that~$G\to
C^{2t+2}$.  In particular, condition ({\it ii\/}) may be strengthened to ({\it
iii\/})~$G\to C^\ell$ for some~$\ell=\ell(G)$.  For~$G=G_t$
above~$\ell=\ell(G)=2t+2=2g(G)-2$. Here, we show that suitable Ramanujan
graphs constructed by Lubotzky, Phillips, and Sarnak~{\refLPS} are explicit
examples of graphs~$G=G_g$ satisfying~({\it i\/}) and~({\it iii\/}) above.
For such graphs~$\ell=\ell(G)$ in~({\it iii\/}) may be taken to be roughly
equal to~$(3/2)g(G)$, thus considerably improving the value~$2g(G)-2$ given in
the result of R\"odl and Tuza. It is not known whether there are graphs~$G$ of
arbitrarily large girth for which~({\it iii\/}) holds
with~$\ell=\ell(G)=g(G)$.
\endabstract
%
% intro.tex
%
\beginsection 1. Introduction

In this note we shall consider proper edge-colourings of graphs, and
we shall 
be concerned with the existence of subgraphs whose edges are all coloured
differently. To be more precise, let a graph~$G$ be given, and
suppose~$\gamma:E(G)\to\N$ is a proper edge-colouring of~$G$.  We shall say
that a subgraph~$H\subset G$ of~$G$ is {\deffont multicoloured\/} with respect
to the colouring~$\gamma$ if~$\gamma$ is injective on~$E(H)$.  A question
raised by Spencer (see~{\refE}, p.~29) is as follows: are there graphs~$G$ of
arbitrarily large girth such that every proper edge-colouring of~$G$ admits a
multicoloured cycle?

Let~$G$ and~$H$ be graphs. We write~$G\mcarrow H$ if for any proper
edge-colouring~$\gamma$ of~$G$ there is a subgraph~$H'\subset G$ of~$G$
isomorphic to~$H$ such that~$\gamma$ is injective on~$E(H')$.  Recently,
R\"odl and Tuza~{\refRoTu} settled the above problem of Spencer in the
affirmative, by proving the following stronger statement. As customary,
we denote the girth of a graph~$G$ by~$g(G)$, and write~$C^\ell$ for a
cycle of length~$\ell\geq3$.

\proclaim Theorem {\RoTu}. For every positive integer~$t$, every
real~$\delta$ such that~$0<\delta<1/(2t+1)$, and every~$n$ sufficiently
large with respect to~$t$ and~$\delta$, there is a graph~$G=G^n$ of
order~$n$ such that ({\it i\/})~$g(G)=t+2$, and ({\it
ii\/})~$G\mcarrow C^\ell$ for all~$2t+2\leq\ell\leq n^\delta$.
\endproclaimsquare

Erd\H os~{\refE} remarked that random methods should be suitable for tackling
Spencer's problem, and indeed in~{\refRoTu} the result above is proved by
probabilistic means. In fact, it is shown that if~$p=n^{\epsilon-1}$
and~$\epsilon=\epsilon(t,\delta)>0$ is appropriately chosen, then a graph~$G$
obtained by suitably altering a random graph~$G_p\in\G(n,p)$ almost surely
satisfies~({\it i\/}) and~({\it ii\/}).  No explicit construction for a
graph~$G$ as in Theorem~{\RoTu} is given in~{\refRoTu}.

Following~{\refRoTu}, for a graph~$H$, let us denote by~$t(H)$ the
smallest possible girth for a graph~$G$ satisfying~$G\mcarrow H$.
Formally, let~$t(H)=\inf\{g(G):G\mcarrow H\}$.  In the spirit of the
well-known works of Ne\v set\v ril and R\"odl~{\refNR}, in {\refRoTu},
R\"odl and Tuza raise the following very attractive problem.

\proclaim Problem {\prob}. Does~$t(H)=g(H)$ hold for every graph~$H$?
\endproclaim

As pointed out in~{\refRoTu}, we do clearly have~$t(H)=g(H)$ if~$H$ is a
forest or if~$H$ contains a triangle. The complete bipartite graph~$K^{4,4}$
shows that~$t(C^4)=4$.  By considering the incidence graph of a projective
plane,
\discard
{\it i.e.\/}~the bipartite graph whose vertex classes correspond to
the points and lines of the plane and where a point and a line are adjacent
if and only if their are incident,
\enddiscard
one may check that~$t(C^6)=6$, and a random construction involving projective
planes gives that~$t(C^5)=5$.  Thus~$t(C^\ell)=\ell$ for~$3\leq\ell\leq6$.
(See Section~5 for details concerning these small cases of~$\ell$.) More
generally, Theorem~{\RoTu} gives
that~$t(C^\ell)\geq\lfloor\ell/2\rfloor+1$ for all~$\ell\geq4$.  Our main
results here significantly improve this estimate on~$t(C^\ell)$ for large even
values of~$\ell$, and give explicit graphs for Spencer's original
problem. 
Indeed, Theorems~{\MainRes} and~{\fixedell} below show that suitable Ramanujan
graphs~$X$ of Lubotzky, Phillips, and Sarnak~{\refLPS} are as required.
Roughly speaking, we take a large enough bipartite $d$-regular~$X$ and show
that~$X\mcarrow C^{2s}$ for all~$s$ varying from about~$(3/4)g(X)$ up
to~$\Omega(d)$. (See Theorem~{\MainRes}.) 
Then the asymptotic lower bound for~$t(C^\ell)$ ($\ell$~even) that we obtain
is~$t(C^{2s})\geq(4/3+o(1))s$. When deducing this bound, we shall arrive at a
simple number-theoretic problem concerning the existence of certain primes. 
Although this question can be dealt with in a standard manner, 
for completeness we include a separate section, Section~4, dedicated to it. 

The methods used in the proof of Theorem~{\MainRes} are different from the
methods used by R\"odl and Tuza; they are based on the eigenvalue method of
Alon and Milman (see, {\it e.g.\/}~{\refAS}, Chapter~9, Section~2) and on the
techniques used by Beck~{\refBeck} to prove that the size-Ramsey number of an
$\ell$-path is~$O(\ell)$. The fact that Ramanujan graphs are `explicit
examples' of extremal or nearly extremal graphs with respect to many problems
is well known, and our result gives another example of such a problem. This
note was inspired by the results of Alon and Chung~{\refAC}, and of Friedman
and Pippenger~{\refFP}. Let us also mention that an extremal problem
concerning the relation~$\mcarrow$ is studied in Babai~{\refBa}, and that the
corresponding problem for uniform hypergraphs is considered in
Lefmann~{\refLef}. Problem~{\prob} is also related to canonical versions of
Ramsey's theorem, in the sense of Erd\H os and Rado~{\refERcan}. 

In the next section we state a few properties of the Ramanujan graphs
constructed by Lubotzky, Phillips, and Sarnak that we shall use, and we give
some lemmas needed in the proof of Theorem~{\MainRes}.  Section~3 is devoted
to the proof of Theorem~{\MainRes}, and in Section~4 we prove
Theorem~{\fixedell}. In Section 5, which is included for completeness,
we prove that $t(C^\ell)=\ell$ for~$3\leq\ell\leq6$. In the last section
we give some generalisations of our results, and we mention a related result. 

Finally, we remark that appropriate modifications of our results here can be
shown to hold for the Ramanujan graphs~$Y_m=Y_{m,p}$ of Margulis~{\refMarg}.
However we have decided to restrict ourselves to the graphs~$X^{p,q}$ because
a more detailed analysis of these graphs is available in the literature.
Moreover, unfortunately, the use of the~$Y_m$ does not seem to give
significantly better results.
%
% sec2.tex
%
\beginsection 2. Auxiliary lemmas

Let~$p$ and~$q$ be two distinct primes such that~$p$, $q\equiv1\;(\mod
4)$, $p\leq q^2$, and~$p$ is not a square in~$\Z/q\Z$. Throughout this
note, except for Section 6, we let~$G=G_{p,q}=X^{p,q}$ be the
Ramanujan graph of Lubotzky, 
Phillips, and Sarnak~{\refLPS}. Thus~$G$ is a bipartite graph, with
bipartition~$V=V(G)=V_0\cup V_1$, say. The order~$|G|$ of~$G$
is~$2n=q(q^2-1)$, and~$G$ is a $d$-regular graph where~$d=p+1$.  We now
recall three important results concerning the graph~$G$.  Let us collect
three important properties of $G$ in the following lemma.

\proclaim Lemma {\Ram}. Let~$G=G_{p,q}=X^{p,q}$ be as above. Then
the following hold.
\item{({\it i\/})}The girth~$g(G)$ of~$G$
satisfies~$4\log_p(q/\surd2)\leq g(G)<4\log_p(q\surd(2p))$. In
particular, setting~$t=\lceil(2/3)\log_p(n/\surd2)\rceil$, we
have~$d>p\geq2^{-1/3t}n^{2/3t}$ and~$g(G)\geq2t$. 
\item{({\it ii\/})}The eigenvalues of the adjacency matrix of~$G$
are ~$\pm\lambda_0,\ldots,\pm\lambda_{n-1}$,
where $0\leq\lambda_{n-1}\leq\cdots\leq\lambda_0=d$,
and~$|\lambda_i|\leq2p^{1/2}=2(d-1)^{1/2}$ for all~$i\not= 0$.
\item{({\it iii\/})}For any~$U\subset V_0$
and any~$W\subset V_1$, the number of edges~$e(U,W)$ between~$U$ and~$W$
satisfies~$\big|e(U,W)-(d/n)|U||W|\big|\leq2\{(d-1)|U||W|\}^{1/2}$.
\endproclaimsquare

Property ({\it ii\/}), often called the {\deffont Ramanujan property\/}, is
proved in~{\refLPS}, together with the lower bound for~$g(G)$ in~({\it i\/}).
The upper bound in~({\it i\/}) is a result of Biggs and Boshier~{\refBiBo}.
Finally, we remark that the technique given in~Alon and Spencer~{\refAS},
Chapter~9, Section~2, is enough to prove~({\it iii\/}).

For the rest of this note, we let~$\epsilon=2\times10^{-6}$, and
set~$\ell=\lceil3t/2\rceil$ where~$t$ is as in Lemma~{\Ram}({\it i\/}).
Our aim is to show that if~$p$ and~$q$ are larger
than a certain absolute constant, $t\geq2$,
and~$d\geq16\epsilon^{-2\ell}$, then~$G=G_{p,q}=X^{p,q}\mcarrow C^{2s}$
for all~$\ell+1\leq s\leq(\epsilon^\ell/6)n^{1/\ell}+1$.

In what follows, several of the inequalities are claimed to hold for
large enough values of~$p$ and~$q$ only. We also assume that~$p$ and~$q$
are so that~$t\geq2$. (For instance, we may require that~$q\geq 3p/2$ to
guarantee that~$t\geq2$.)  Note that, in particular, we have~$d\geq
d_0=2^{-1/6}n^{2/3t}$.  Below, our indices will be taken modulo~$2$ so
that, {\it e.g.\/}~$V_0=V_2=\ldots\,$, {\it etc\/}.

For convenience, we introduce the following simple definition. Let~$J$ be a
bipartite graph with a fixed bipartition, say~$V(J)=X\cup Y$, and let $b$
and $f$ be positive real numbers. Then we shall
say that~$J$ is a {\deffont$(b,f)$-expander\/} if for all~$U\subset X$
and~$U\subset Y$ such that~$|U|\leq b$ we have~$|\Gamma_J(U)|\geq f|U|$.  Note
that for a $(b,f)$-expander~$J$ if~$V(J)\neq\emptyset$ and~$f>1$, then~$|X|$,
$|Y|>b$.

If~$H$ is a graph and~$U$, $W\subset V(H)$ are disjoint sets of vertices,
we write $H[U,W]$ for the bipartite subgraph of~$H$ with vertex
set~$U\cup W$ and edge set $E_H(U,W)=\{uw\in E(H):u\in U,\,w\in W\}$.
Also, if~$A$, $B\subset V(H)$, then $e(A,B)=e_H(A,B)$ denotes the number
of edges in~$H$ that have one endvertex in~$A$ and the other in~$B$.  As
usual, we denote the minimal degree $\min_{x\in H}d_H(x)$ of the
graph~$H$ by~$\delta(H)$.  Recall $G=G_{p,q}=X^{p,q}$ has
order~$2n=q(q^2-1)$. Throughout this note, we let~$r=n/2$. Note that
clearly $n=q(q^2-1)/2$ is even, and hence~$r$ is an integer.  We are now
ready to state and prove our first lemma.

\proclaim Lemma~{\Beck}. Suppose~$d\geq360^2$. Let~$S_\sigma\subset
V_\sigma$ with~$|S_\sigma|=r=n/2$ $(\sigma=0,\,1)$ be given.  Let~$H\subset
G'= G[S_0,S_1]$ be a spanning subgraph of~$G'$ such
that~$e(H)\geq(1/3)e(G')$. Then there are sets~$\bS_\sigma\subset
S_\sigma$ $(\sigma=0,\,1)$ such that if~$J=H[\bS_0,\bS_1]$, then ({\it
i\/})~$\delta(J)\geq d/18$, and ({\it ii\/})~$J$ is an
$(r/10f,f)$-expander for any~$0<f\leq360^{-2}d$. In particular, we
have~$|\bS_\sigma|\geq n/20$ $(\sigma=0,\,1)$.
\endproclaim
\proof
Let~$d'=e(G')/r$ be the average degree of~$G'=G[S_0,S_1]$. Note that
as~$d\geq144$, we have~$d'\geq d/3$. Let~$Z\subset S_0\cup S_1$ be a minimal
non-empty set satisfying~$e(H[Z])\geq(1/6)d'|Z|$.  Let~$\bS_\sigma=Z\cap
S_\sigma$ ($\sigma=0,\,1$), and let~$J=H[\bS_0,\bS_1]$. Then, for
any~$X\subset Z$, we have~$e_J(X,Z)\geq(1/6)d'|X|$. Indeed, we
have~$e_J(X,Z)=e(H[Z])-e(H[Z\setminus X])\geq(d'/6)|Z|-(d'/6)|Z\setminus
X|=(d'/6)|X|$.  Noting that for~$x\in Z=V(J)$ we have~$d_J(x)=e_J(\{x\},Z)$,
we see that $\delta(J)=\min_{x\in J}d_J(x)\geq d'/6\geq d/18$, which
proves~({\it 
i\/}).

Now assume~$0<f\leq360^{-2}d$. We shall show that~$J$ is an
$(r/10f,f)$-expander.  Suppose~$U\subset\bS_\sigma$,
where~$\sigma=0$ or~$1$, and~$u=|U|\leq r/10f$.
Let~$W=\Gamma_J(U)\subset\bS_{\sigma+1}$, and set~$w=|W|$. We
claim that~$w\geq fu$. Suppose for a contradiction that~$w<fu$.
Then~$du/18\leq d'u/6\leq e_J(U,Z)=e_J(U,W)\leq
e_G(U,W)\leq(d/n)uw+2(duw)^{1/2}<du/20+2(duw)^{1/2}$, 
and hence~$w\geq360^{-2}du\geq fu$, which is a contradiction.

To see that~$|\bS_\sigma|\geq n/20$ ($\sigma=0,\,1$), it suffices to note
that~$f_0=360^{-2}d>1$. Indeed, as~$J$ is an $(r/10f,f)$-expander for
all~$0<f\leq f_0$, we have~$|\bS_\sigma|>r/10f$ ($\sigma=0,\,1$) for
all~$1<f\leq f_0$. Letting~$f$ tend to~$1$, we conclude
that~$|\bS_\sigma|\geq r/10$ ($\sigma=0,\,1$).
\endproof

We now let~$\gamma:E(G)\to\N$ be an arbitrary fixed proper edge-colouring
of~$G=G_{p,q}$. Let~$S_\sigma\subset V_{\sigma}$ such that~$|S_\sigma|=r=n/2$
($\sigma=0,\,1$) be given. Also, let~$H\subset G'= G[S_0,S_1]$ be a
spanning subgraph of~$G'$ such that~$e(H)\geq(1/3)e(G')$.
Suppose~$\bS_\sigma\subset S_\sigma$ ($\sigma=0,\,1$) are as in
Lemma~{\Beck}, and again let~$J=H[\bS_0,\bS_1]$.

For tidiness, if~$P\subset G$ is a path, we write~$\gamma(P)$
for~$\gamma(E(P))$, and say that~$\gamma$ is injective on~$P$ if
it is injective on~$E(P)$.  We may now state and prove the key
lemma needed in the proof of our main result.

\proclaim Lemma {\MainLemma}. Suppose~$\ell\leq\ell'\leq\epsilon
n^{1/\ell}$. Let~$c_0\in\N$, and~$x\in\bS_\sigma$ $(\sigma=0$ or~$1)$ be
given. Then there is a set~$T\subset\bS_{\sigma+\ell'}$ such that ({\it
i\/})~$|T|\geq\epsilon^\ell n$, and ({\it ii\/})~for all~$y\in T$ there
is an $x$--$y$~path~$P_y$ of length~$\ell'$ in~$J$ with ({\it
a\/})~$c_0\notin\gamma(P_y)$, and ({\it b\/})~$\gamma$ injective
on~$P_y$.
\endproclaim
\proof
First recall that the minimal degree~$\delta(J)$ of~$J$
satisfies~$\delta(J)\geq d/18\geq3\ell'$. Thus clearly there is a
path~$P_0\subset J$ in~$J$, starting at~$x$, of length~$\ell'-\ell$, such
that ({\it a\/})~$c_0\notin\gamma(P_0)$, and ({\it b\/})~$\gamma$ is
injective on~$P_0$. Suppose~$P_0$ is an $x$--$x'$~path, and note
that~$x'\in S_{\sigma'}$, where~$\sigma'=\sigma+\ell'-\ell$.
We now let~$d'_0=d_0$ if~$t$ is even, and
let~$d'_0=2^{-1/6}n^{1/\ell}$ if~$t$ is odd. Note that clearly~$d'_0\leq
d_0\leq d$. 

Let~$N_0=\{x'\}$. Let~$1\leq i\leq\ell$, and suppose that pairwise
disjoint sets~$N_j\subset\bS_0\cup\bS_1$ ($0\leq j<i$) have been defined
so that, for every~$0\leq j<i$, we have
\item{({\it i\/})}$N_j\subset S_{\sigma'+j}$,
\item{({\it ii\/})}
   $|N_j|=\left\lceil\(d'_0/3\times360^2\)^j\right\rceil$,  
\item{({\it iii\/})}for all~$z\in N_j$, there is an $x'$--$z$~path~$P_z$
in~$J$ such that ({\it a\/})~$V(P_0)\cap V(P_z)=\{x'\}$, ({\it
b\/})~$|V(P_z)\cap N_k|=1$ ($0\leq k\leq j$), and ({\it
c\/})~$P'_z=P_0P_z$ is an $x$--$z$~path in~$J$
with~$c_0\notin\gamma(P'_z)$ and~$\gamma$ injective on~$P'_z$.

\noindent We shall now extend the sequence~$N_j$ ($0\leq j<i$) by
defining~$N_i\subset\bS_0\cup\bS_1$ suitably. Let~$U=N_{i-1}$,
$W=\Gamma_J(U)$, and~$f=d'_0/360^2$. Note
that~$|U|=\left\lceil\(d'_0/3\times360^2\)^{i-1}\right\rceil\leq r/10f$, 
and hence~$|W|\geq f|U|$.
Let~$W'=W\cap\(V(P_0)\cup\bigcup_{j=0}^{i-1}N_j\)$. Then we have
$$
|W'|\leq\left\lceil{1\over2}\(\ell'-\ell+1\)\right\rceil
              +\sum_{j=0}^{i-2}|N_j|\leq\ell'-1+2|N_{i-2}|.
$$
For each~$z\in N_{i-1}$, fix an $x'$--$z$~path~$P_z\subset J$ as in~({\it
iii\/}) above, and let~$P'_z=P_0P_z$. Now let
$$
W''=\bigcup_{z\in N_{i-1}}\big\{w\in\Gamma_J(z):
              \gamma(zw)\in\{c_0\}\cup\gamma(P'_z)\big\}.
$$
Then~$|W''|\leq\sum_{z\in N_{i-1}}(1+|\gamma(P'_z)|)\leq\ell'|N_{i-1}|$.
Let~$N'_i=W\setminus(W'\cup W'')$. Then
$$
\eqalign{
|N'_i|&\geq|W|-(|W'|+|W''|)
         \geq|W|-\(\ell'-1+2|N_{i-2}|+\ell'|N_{i-1}|\)\cr
   &\qquad\qquad\qquad\geq f|N_{i-1}|-2\ell'|N_{i-1}| 
         \geq{d'_0\over3\times360^2}|N_{i-1}|
           \geq\(d'_0\over3\times360^2\)^i.\cr 
} 
$$ 
Let~$N_i\subset N'_i$ be such
that~$|N_i|=\left\lceil\(d'_0/3\times360^2\)^i\right\rceil$. Note that
then ({\it i\/}), ({\it ii\/}), and~({\it iii\/}) hold for~$j=i$. Thus by
induction there are sets~$N_j$ ($0\leq j\leq\ell$) satisfying~({\it
i\/}), ({\it ii\/}), and~({\it iii\/}) for all~$0\leq j\leq\ell$. To
finish the proof, let~$T=N_\ell$.
\endproof
%
% sec3.tex
%
\beginsection 3. The main result

As in the previous section, we let a proper
edge-colouring~$\gamma:E(G)\to\N$ be fixed. Let the partition of~$E=E(G)$
naturally induced by~$\gamma$ be~$E=E_1\cup\cdots\cup E_k$, where, say,
$E_i=\gamma^{-1}(\{i\})\neq\emptyset$ ($1\leq i\leq k$). For the rest of
this section, let~$V_\sigma=\S0_\sigma\cup\S1_\sigma$,
with~$|\S0_\sigma|=|\S1_\sigma|=r=n/2$, be a fixed partition
of~$V_\sigma$ ($\sigma=0,\,1$). Let~$G^{(i)}=G[\S{i}_0,\S{i}_1]$
($i=0,\,1$).

We shall use the following slightly non-standard notation. If~$H$ is a
graph and~$F\subset E(H)$, we write~$H[F]$ for the {\it spanning\/}
subgraph of~$H$ with edge set~$F$. The following result is a simple
technical lemma. 

\proclaim Lemma {\splitting}. Suppose~$d\geq108\log3$. Then
there exists a partition~$[k]=C_0\cup C_1$ of~$[k]=\{1,\ldots,k\}$ such that
if we let~$H^{(i)}=G^{(i)}\[E(G^{(i)})\cap\bigcup_{j\in C_i}E_j\]$
$(i=0,\,1)$, then~$e(H^{(i)})\geq(1/3)e(G^{(i)})$ $(i=0,\,1)$.
\endproclaim
\proof
Set~$a_i^{(j)}=|E_i\cap E(G^{(j)})|$ for~$1\leq i\leq k$ and~$j=0,\,1$.  Note
that~$0\leq a_i^{(j)}\leq r$. Put~$i\in[k]$ in~$C_0$ with probability~$1/2$,
independently from all other~$j\in[k]$.  Let~$X_i=1$ if~$i\in C_0$ and~$X_i=0$
if~$i\in C_1$. Let~$H^{(i)}$ ($i=0,\,1$) be as in the statement of our lemma.
Then clearly~$e(H^{(0)})=\sum_{1\leq i\leq k}a_i^{(0)}X_i$.
Let~$Y_i=a_i^{(0)}X_i/r$ ($1\leq i\leq k$), and set~$Y=\sum_{1\leq i\leq
k}Y_i$. Then, for any~$0\leq\delta\leq1$, by Hoeffding's inequality we have
that~$\P\{Y\leq(1-\delta)\E(Y)\}\leq\exp\{-\delta^2\E(Y)/2\}$.  Note
that~$\E(Y)=e(G^{(0)})/2r\geq d/6\geq18\log3$, and therefore we have that
$\P\{e(H^{(0)})\leq(1/3)e(G^{(0)})\}\leq1/3$.  Similarly
$\P\{e(H^{(1)})\leq(1/3)e(G^{(1)})\}\leq1/3$, and thus a partition as required
does exist.
\endproof

We are now ready to prove our main result.

\proclaim Theorem {\MainRes}. Let~$p$ and~$q$ be distinct primes such
that~$p$, $q\equiv1\;(\mod 4)$, $q^2\geq p$, and~$p$ is not a square
in~$\Z/q\Z$.  Let~$n=q(q^2-1)/2$, $t=\lceil(2/3)\log_p(n/\surd2)\rceil$,
$\ell=\lceil3t/2\rceil$, and~$\epsilon=2\times10^{-6}$. Suppose~$t\geq2$,
$d=p+1\geq16\epsilon^{-2\ell}$, and let~$G=G^{2n}=X^{p,q}$.  Then,
if~$\ell+1\leq s\leq(\epsilon^\ell/6)n^{1/\ell}+1$, we have~$G\mcarrow
C^{2s}$.
\endproclaim
\proof
Recall that a partition~$V_\sigma=S^{(0)}_\sigma\cup S^{(1)}_\sigma$
with~$|S^{(0)}_\sigma|=|S^{(1)}_\sigma|=r=n/2$ of~$V_\sigma$ ($\sigma=0,\,1$) has
been fixed. Let us now fix~$C_i$ and~$H^{(i)}$ ($i=0,\,1$) as in
Lemma~{\splitting}. For both~$i=0,\,1$, we apply Lemma~{\Beck} to
obtain~$\bS_\sigma^{(i)}\subset S_\sigma^{(i)}$ with~$|\bS_\sigma^{(i)}|\geq
n/20$ ($\sigma=0,\,1$) such that~$J^{(i)}=H^{(i)}[\bS_0^{(i)},\bS_1^{(i)}]$ is
an $(r/10f,f)$-expander for all~$0<f\leq d/360^2$. Since~$|\bS_0^{(0)}|$,
$|\bS_1^{(1)}|\geq n/20$, we have~$e_G(\bS_0^{(0)},\bS_1^{(1)})>0$.
Let~$x_0x_1\in E(G)$ be such that~$x_0\in\bS_0^{(0)}$ and~$x_1\in\bS_1^{(1)}$.
Let~$c_0=\gamma(x_0x_1)$, and
suppose~$\ell\leq\ell'\leq(\epsilon^\ell/6)n^{1/\ell}\leq\epsilon n^{1/\ell}$.
We shall now proceed to find a multicoloured $2s$-cycle~$C^{2s}\subset G$
where~$s=\ell'+1$.

We first apply Lemma~{\MainLemma} to~$J^{(i)}$ ($i=0,\,1$) and
obtain~$T^{(i)}\subset\bS_{i+\ell'}$ such that ({\it
i\/})~$|T^{(i)}|=a=\lceil\epsilon^\ell n\rceil$, and ({\it ii\/})~for
all~$y_i\in T^{(i)}$, there is an $x_i$--$y_i$~path~$P_{y_i}
\subset J^{(i)}$ in~$J^{(i)}$ of length~$\ell'$ with~$\gamma$ injective
on~$P_{y_i}$ and~$c_0\notin\gamma(P_{y_i})$. 

For each~$y_i\in T^{(i)}$ ($i=0,\,1$), fix an
$x_i$--$y_i$~path~$P_{y_i}\subset J^{(i)}$ as given in~({\it ii\/})
above. We now notice that, since~$d\geq16\epsilon^{-2\ell}$, we
have~$e_G(T^{(0)},T^{(1)})\geq(d/n)a^2-2d^{1/2}a\geq(d/2n)a^2$. For~$i=0,\,1$,
let 
$$
F_i=\bigcup_{y_i\in T^{(i)}}\big\{y_iz\in E(G):z\in T^{(i+1)},
             \hbox{ and }\gamma(y_iz)\in\{c_0\}\cup\gamma(P_{y_i})\big\}, 
$$
and set~$F=F_0\cup F_1$. Then~$|F|\leq(\ell'+1)|T^{(0)}\cup T^{(1)}|
\leq2(\ell'+1)a$. Note that since~$\ell\geq3$
and~$d\geq16\epsilon^{-2\ell}$, we have~$\epsilon^\ell d\geq2\times10^{18}$.  
Thus~$\ell'+1\leq(\epsilon^\ell/6)n^{1/\ell}+1
\leq(\epsilon^\ell/6)2^{1/6}d+1<(\epsilon^\ell/4)d$, and
therefore~$|E_G(T^{(0)},T^{(1)})\setminus F|\geq(d/2n)a^2-2(\ell'+1)a
=a\(\epsilon^\ell d/2-2(\ell'+1)\)>0$.  Finally, suppose~$y_0y_1\in
E_G(T^{(0)},T^{(1)})\setminus F$. Then, if~$P_{y_0}=x_0z_1z_2\ldots y_0$,
$P_{y_1}=x_1z'_1z'_2\ldots y_1$, we have that~$C=x_0z_1z_1\ldots y_0y_1\ldots
z'_2z'_1x_1x_0$ is a $2s$-cycle in~$G$ and~$\gamma$ is injective on~$E(C)$.
This finishes the proof of the theorem.
\endproof

Recall that for~$G$ as in Theorem~{\MainRes} we have~$g(G)\geq2t$, and in
fact~$g(G)$ is roughly equal to~$2t$ (cf.~Lemma~{\Ram}({\it i\/})). Thus
in the above result we have~$G\mcarrow C^{2s}$ for~$2s$
about~$(3/2)g(G)$. Notice, in fact, that this means that the {\it short\/}
multicoloured cycles guaranteed by
Theorem~{\MainRes} are necessarily induced. Moreover, note 
that if~$\ell$ is not too large, then 
the upper bound for~$s$ in Theorem~{\MainRes} is nearly of the same
order as~$d=p+1$.
Thus, since the chromatic index of~$G$ is~$d$, the
restriction that~$s$ should not exceed~$(\epsilon^\ell/6)n^{1/\ell}+1$
cannot be essentially weakened.
%
% sec4n.tex
%
\beginsection 4. The existence of suitable primes

Theorem~{\MainRes} states that~$X=X^{p,q}\mcarrow C^{2s}$ provided~$p$, $q$,
and~$s$ satisfy certain conditions. For brevity, let us say that a
pair~$(p,q)$ of primes is {\deffont good\/} if~$p$, $q\equiv1\;(\mod4)$,
$q\geq2p$, and~$p$ is a quadratic non-residue modulo~$q$. Note that {\it a
priori\/} it is not clear that there is any good pair~$(p,q)$ of primes that
admits an integer~$s$ satisfying the conditions in Theorem~{\MainRes}.  Our
first aim in this section is to present a simple result, Lemma~{\primelemma},
that implies that for any even~$\ell\geq18$ there is a good pair~$(p,q)$ such
that~$X=X^{p,q}\mcarrow C^\ell$ (see Theorem~{\fixedell}). Moreover, we shall
see that we may further require the girth~$g(X)$ of~$X$ to be roughly as large
as~$(2/3)\ell$.

As usual, for an integer~$n\geq1$, let~$\phi(n)$ denote the number of 
integers~$1\leq m\leq n$ coprime to~$n$. Also, let~$\Lambda(n)=\log p$
if~$n$ is a positive integer power of a prime~$p$, and let~$\Lambda(n)=0$  
otherwise. Let a real~$x>0$ and integers~$h\geq2$, $a\geq1$ be given.
We put
$$
\psi(x;h,a)=\sum\{\Lambda(n):2\leq n\leq x,\;n\equiv a\;(\mod h)\}. 
$$
A well-known number-theoretic result states
that~$\psi(x;h,a)=(1+o(1))x/\phi(h)$ as~$x\to\infty$, provided~$h$ and~$a$ are
fixed and~$(a,h)=1$. In fact, the following refinement of Dirichlet's
celebrated theorem on primes in arithmetic progressions is an easy consequence
of the above result. For fixed~$h$ and~$a$ with~$(a,h)=1$, we
have~$\pi(x;h,a)=(1+o(1))x/\phi(h)\log x$ ($x\to\infty$), where~$\pi(x;h,a)$
is the number of primes~$2\leq p\leq x$ with~$p\equiv a\;(\mod h)$. We refer
the reader to Davenport~{\refDave} for this and other related results from
analytic number theory.

Below, we shall be interested in the error term in the above asymptotic
estimate for~$\psi(x;h,a)$. Let us introduce some notation.  We
put~$E(x;h,a)=|\psi(x;h,a)-x/\phi(h)|$, $E(x,h)=\max\{E(x;h,a):(a,h)=1\}$,
and~$E^*(x,h)=\max\{E(y,h):0<y\leq x\}$. The following beautiful and
far-reaching result was proved by Bombieri~{\refBomb} (see also
Davenport~{\refDave}, \Section28).

\proclaim Theorem {\Bomb}. Let~$A>0$ be fixed. Then there is a
constant~$C=C(A)$ such that, for~$x^{1/2}(\log x)^{-A}\leq
Q\leq x^{1/2}$, we have~$\sum_{2\leq h\leq Q}E^*(x,h)\leq 
Cx^{1/2}Q(\log x)^5$. 
\endproclaimsquare

In particular, the above result implies that~$E^*(x,h)$ is a great deal
smaller than~$x/\phi(h)$ for most~$h\leq x^{1/2}(\log x)^{-A}$. Furthermore,
clearly, Theorem~{\Bomb} states that under the given conditions the average
error~$\Ave_{2\leq h\leq Q}E^*(x,h)$ is~$O\big\{x^{1/2}(\log x)^5\big\}$.  We
remark in passing that assuming the generalised Riemann hypothesis, one may
prove that~$E(x,h)=O\big\{x^{1/2}(\log x)^2\big\}$ for~$x\geq h$
(cf.~\Section20 in~{\refDave}). Such a bound for~$E(x,h)$ would allow us to
give a more direct proof of the existence of appropriate good pairs of primes. 

The main lemma of this section is Lemma~{\primelemma}.  For its proof we shall
need the following simple result. For~$x>0$ put~$\psi_2(x)=\sum\Lambda(n)$,
where the sum is extended over all~$2\leq n=p^k\leq x$ with~$p$ a prime
and~$k\geq2$ an integer. Then, by the prime number theorem, we have
that~$\psi_2(x)\leq (2+o(1))x^{1/2}$ as~$x\to\infty$.  Let us now turn to
Lemma~{\primelemma}. Suppose a set~$H=\{h_i\in\N:i\geq1\}$ of integers is
fixed, and assume~$2\leq h_1<h_2<\cdots\;$. Moreover, let integers~$1\leq
a_i<h_i$ ($i\geq1$) be given.

\proclaim Lemma {\primelemma}. Suppose that for a constant~$\rho>0$ we
have~$|H\cap[n]|=(\rho+o(1))n/\log n$ as~$n\to\infty$. Let~$0<\eta<1/2$
and~$b>0$ be fixed. Then there is~$h_i\in H$ and a prime~$q$ such
that~$h_i\geq b$, $q\equiv a_i\;(\mod h_i)$, and~$(h_i/4)^{1/\eta}/4\leq
q\leq(h_i/4)^{1/\eta}$.
\endproclaim
\proof
Let~$A=7$ in Theorem~{\Bomb}, and set~$C=C(7)$. Pick~$Q\geq2$, and
let~$x_0=x_0(Q)$ be such that~$Q=x_0^{1/2}(\log x_0)^{-7}$. Assume that~$Q$ is
sufficiently large so that ({\it i\/})~$4x_0^{\eta}\geq b$, ({\it ii\/})~$\log
x_0\geq(80C/\rho)2^\eta$, ({\it iii\/})~$x_0^{1/2-\eta}\geq60\times2^\eta$,
and ({\it iv\/})~$\psi_2(x_0)\leq3x_0^{1/2}$. Now note that, as~$x\to\infty$,
$$
\eqalign{
N(x)&=\big|\{h\in H:4x^\eta<h\leq4(2x)^\eta\}\big| \cr
    &=(4\rho+o(1)){(2x)^\eta\over\eta\log(2x)}
      -(4\rho+o(1)){x^\eta\over\eta\log x}, \cr
}
$$
which is, for large enough~$x$, at least
$$
{4\rho x^\eta\over\eta\log x}\(2^{3\eta/4}-2^{\eta/4}\)
  \geq2\rho(\log2)x^\eta(\log x)^{-1}
   \geq\rho x^\eta(\log x)^{-1}.
$$
Thus we may further assume that~$Q$ is sufficiently large to guarantee
that~$N(x_0)\geq\rho x_0^\eta(\log x_0)^{-1}$. Now, by Theorem~{\Bomb}, 
we clearly have 
that~$E^*(x_0,h)\geq(2C/\rho)x_0^{1-\eta}(\log x_0)^{-1}$ holds
for at most~$(\rho/2)x_0^\eta(\log x_0)^{-1}$ values of~$2\leq h\leq
Q$. Thus there is~$h_i\in H$ such that~$b\leq4x_0^\eta<h_i\leq4(2x_0)^\eta$,
and~$E^*(x_0,h_i)\leq(2C/\rho)x_0^{1-\eta}(\log x_0)^{-1}$.  Hence we
have~$E(x_0;h_i,a_i)$, $E(x_0/2;h_i,a_i)\leq(2C/\rho)x_0^{1-\eta}(\log
x_0)^{-1}$. Therefore
$$
\eqalign{
\psi(x_0;h_i,a_i)-\psi(x_0/2;h_i,a_i)
   &\geq{x_0\over2\phi(h_i)}-{4C\over\rho}
             \cdot{x_0^{1-\eta}\over\log x_0}\cr
   &\qquad\geq{x_0\over10\phi(h_i)}+\psi_2(x_0)>\psi_2(x_0),\cr
}
$$
where for the second inequality we use~({\it ii\/}) and~({\it iii\/}) 
above. Thus there is a prime~$q$ such that~$x_0/2<q\leq x_0$ and
$q\equiv a_i\;(\mod h_i)$. Finally, note 
that~$(h_i/4)^{1/\eta}/4\leq x_0/2<q\leq x_0\leq(h_i/4)^{1/\eta}$.
\endproof

We now apply the above lemma to our particular set-up.  For~$a$, $b\geq2$,
let~$\ell(a,b)=\lceil(3/2)\lceil(2/3)\log_a(n(b)/\surd2)\rceil\rceil$,
where~$n(b)=b(b^2-1)/2$. Note that in Theorem~{\MainRes}, we
have~$\ell=\ell(p,q)$. 

\proclaim Lemma {\pqs}. Let~$P\geq2$ and~$\ell_0\geq8$ be given. Then
({\it i\/})~if~$\ell_0\equiv0$ or~$2\;(\mod3)$, there is 
a good pair~$(p,q)$ of primes with~$p\geq P$ and~$\ell(p,q)=\ell_0$, and
({\it ii\/})~if~$\ell_0\equiv1\;(\mod3)$, then there is a good 
pair~$(p,q)$ of primes with~$p\geq P$ and~$\ell(p,q)=\ell_0+1$. 
\endproclaim
\proof
({\it i\/})~We may clearly assume that~$P\geq53$.  Let~$p_i$ ($i\geq1$) be the
$i$th prime congruent to~$1$ modulo~$4$.  Let~$h_i=4p_i$, and
set~$H=\{h_i:i\geq1\}$. Note that~$H\cap[n]=\{h_i=4p_i:p_i\leq n/4\}$, and
so~$|H\cap[n]|=\pi(n/4;4,1)$. Thus~$|H\cap[n]|=(1/8+o(1))n/\log n$
as~$n\to\infty$.  Now let~$1\leq s_i<p_i$ ($i\geq1$) be such
that~$4s_i\equiv1\;(\mod p_i)$, and let~$1\leq r_i<p_i$ ($i\geq1$) be a
quadratic non-residue modulo~$p_i$. Let~$1\leq a_i<h_i$ ($i\geq1$) be such
that~$a_i\equiv4s_ir_i+p_i\;(\mod h_i)$. We now define~$0<\eta<1/2$ as
follows. If~$\ell_0\equiv0\;(\mod3)$, we let~$\eta=3/\ell_0$, and
if~$\ell_0\equiv2\;(\mod3)$, we let~$\eta=6/(2\ell_0-1)$.  Set~$b=4P$.
Lemma~{\primelemma} then gives that, for some~$i\geq1$ and some prime~$q$, we
have~$p_i\geq P$, $q\equiv4s_ir_i+p_i\;(\mod 4p_i)$,
and~$(1/4)p_i^{1/\eta}\leq q\leq p_i^{1/\eta}$. But then~$q\equiv1\;(\mod4)$
and~$q$ is a quadratic non-residue modulo~$p_i$.  By the law of quadratic
reciprocity, we have that~$p_i$ is a quadratic non-residue modulo~$q$.
Since~$\eta<1/2$, we may deduce from~$q\geq(1/4)p_i^{1/\eta}$
that~$q\geq2p_i$.  Thus~$(p_i,q)$ is good.  Moreover, a simple but a little
tedious calculation shows that indeed~$\ell(p_i,q)=\ell_0$ (the
assumption $P\geq 53$ is used here). This finishes the
proof of~({\it i\/}). Assertion~({\it ii\/}) follows immediately from~({\it
i\/}). 
\endproof

With Lemma~{\pqs} in hand, we may easily show that for any even~$L\geq18$
there is a good pair~$(p,q)$ such that~$X^{p,q}\mcarrow C^L$.

\proclaim Theorem {\fixedell}. Suppose~$s\geq9$ and~$L=2s$. Then 
there is a good pair~$(p,q)$ of primes such that ({\it
i\/})~$X=X^{p,q}\mcarrow C^L$, and ({\it ii\/})~$g(X)\geq(2/3)(L-4)$
if~$s\equiv0$ or~$1\;(\mod3)$ and~$g(X)\geq(2/3)(L-2)$ otherwise.
\endproclaimsquare
%
% sec5n.tex
%
\beginsection 5. Very short multicoloured cycles

In the introduction we remarked that we have~$t(C^\ell)=\ell$ for
all~$3\leq\ell\leq6$. For~$\ell\in\{3,4\}$ this statement can be verified by
considering the complete graph~$K^{14}$ and the complete bipartite
graph~$K^{4,4}$. Now, for~$\ell=6$ we take a projective plane~$\cP$ of large
order, and consider its incidence bipartite graph, namely, the bipartite
graph~$I=I(\cP)$ with vertex classes~$V_0$, $V_1$, where~$V_0=V_0(\cP)$ is the
set of points of~$\cP$ and~$V_1=V_1(\cP)$ is the set of lines of~$\cP$, and
with~$xy\in E(I)$ ($x\in V_0$, $y\in V_1$) if and only if~$x$ and~$y$ are
incident in~$\cP$. By estimating the maximal possible number of
non-multicoloured $6$-cycles in a properly edge-coloured~$I=I(\cP)$, we may
verify that~$I\mcarrow C^6$ for a large enough~$\cP$. Since~$g(I)=6$, we
conclude that~$t(C^6)=6$.

For completeness, we check here that~$t(C^5)=5$: using probabilistic methods
we shall `construct' a suitable graph~$G$ to verify this fact.  Our method of
proof might be of some use to prove upper bounds for~$t(C^\ell)$ for large
odd~$\ell$. Our random construction of~$G$ is based again on large projective
planes~$\cP$. 

\medskip
\noindent{\it The construction of~$G$\/}.\enspace
Let~$\cP$ be a projective plane of order~$q$, and let~$n=q^2+q+1$. Thus~$I$ is
a $(q+1)$-regular bipartite graph and we
have~$|V_0|=|V_0(\cP)|=|V_1|=|V_1(\cP)|=n$. By considering random partitions,
we may assume that~$V_0=A_0\cup A_1\cup A_2$, $V_1=B_1\cup B_2$ are partitions
of~$V_0$ and~$V_1$ such that, for all~$i\in\{0,1,2\}$ and~$j\in\{1,2\}$, we
have ({\it i\/})~$n/6\leq|A_i|\leq n/2$, $n/3\leq|B_j|\leq 2n/3$, and ({\it
ii\/})~$|\Gamma_I(x)\cap B_j|\geq(q+1)/3$ for all~$x\in V_0$,
and~$|\Gamma_I(y)\cap A_i|\geq(q+1)/4$ for all~$y\in V_1$.

We next define~$H\subset I$ by deleting the edges
in~$E_I(A_1,B_2)\cup E_I(A_2,B_1)$ from~$I$. 
Now let~$p=\omega/n$, where~$\omega=\omega(n)=4\log n$. For all
pairs~$(a_1,a_2)\in A_1\times A_2$, add the edge~$a_1a_2$ to~$H$ independently
with probability~$p$, and let~$J$ be the resulting random graph.
Our aim now is to verify that, almost surely, we may delete some edges
from~$E_J(A_1,B_1)\cup E_J(A_2,B_2)\cup E_J(A_1,A_2)$ from~$J$ in such a way
that the resulting graph~$G$ is such that ({\it
iii\/})~$|\Gamma_G(y)\cap A_i|\geq(q+1)/5$ for all~$y\in V_1$,
$i\in\{1,2\}$, ({\it iv\/})~for any~$U\subset A_1$, $W\subset A_2$ with~$|U|$,
$|W|\geq n/15$, we have~$e_G(U,W)\geq p|U||W|/2$, and ({\it v\/})~all
vertices~$z\in A_1\cup A_2$ have degree~$d_{G[A_1,A_2]}(z)=O(\omega)$
in~$G[A_1,A_2]$.

Let us choose which edges from~$E_J(A_1,B_1)$ we shall delete.  To this end,
we first concentrate our attention on a vertex~$y\in B_1$.  Choose a maximum
collection of edge-disjoint quadrilaterals~$C^4\subset J[A_1,A_2\cup\{y\}]$
that contain~$y$, and let~$E_y$ be the edges incident to~$y$ present in this
collection. The edges we delete from~$E_J(A_1,B_1)$ are the ones
in~$E_1=\bigcup_{y\in B_1}E_y$. In exactly the same way, we define a
set~$E_2\subset E_J(A_2,B_2)$ of edges of~$J$ to be deleted from~$J$.

Finally, let~$E_{12}\subset E_J(A_1,A_2)$ be the set of all the edges present
in $4$-cycles~$C^4\subset J[A_1,A_2]$. Define now~$G$ to be the
subgraph~$G=J-(E_1\cup E_2\cup E_{12})$ of~$J$. It is quite easy to
check that~({\it iii\/}), ({\it iv\/}), and~({\it v\/}) above hold in~$G$
almost surely. Let us fix~$G$ satisfying such conditions. This completes the
`construction' of~$G$. 

\claim We have~$g(G)=5$ and~$G\mcarrow C^5$. 
\endclaim
\proofoftheclaim
It is immediate that~$g(G)\geq5$.  To verify the second assertion in our
claim, we use the counting argument of R\"odl and Tuza~{\refRoTu}, which
applies very easily here owing to our definition of~$G$.  It is easily seen
that any vertex~$a_0\in A_0$ belongs to~$\Omega(\omega n)$ cycles~$C^5\subset
G$, and hence the total number of copies of~$C^5$ in~$G$ is~$\Omega(\omega
n^2)$. Let now~$\gamma:E(G)\to\N$ be a fixed proper edge-colouring of~$G$, and
let us count the number of non-multicoloured~$C^5$ contained in~$G$. Let us
write~$a_0b_1a_1a_2b_2$ for a $5$-cycle of~$G$, where naturally~$a_i\in A_i$
and~$b_j\in B_j$ ($i\in\{0,1,2\}$, $j\in\{1,2\}$). How many such~$C^5$ have
the edges~$a_0b_1$ and~$a_2b_2$ of the same colour? For such cycles, the
number of possibilities for~$a_0b_1$ is~$O(n^{3/2})$ and for~$a_0b_2$,
given~$a_0b_1$, is~$O(n^{1/2})$. Also, given~$a_0b_1$ and~$a_0b_2$, there is
at most one possibility for~$a_2b_2$ as this edge must be incident to~$b_2$
and must have the same colour as~$a_0b_1$. Finally, there is at most one
vertex~$a_1\in A_1$ with~$a_1a_2$, $a_1b_1\in E(G)$. Thus the total number of
$5$-cycles~$a_0b_1a_1a_2b_2$ in~$G$ with the edges~$a_0b_1$, $a_2b_2$ of the
same colour is~$O(n^2)$. Analysing a few more cases, one checks that the
number of non-multicoloured $5$-cycles in~$G$ is~$O(n^2)$.  Since the total
number of $5$-cycles in $G$ is~$\Omega(\omega n^2)$, we are done.
\endproofoftheclaimsquare

In view of our results for~$t(C^\ell)$ for~$\ell$ even, the method above might
apply to give improved lower estimates for~$t(C^\ell)$ for large odd~$\ell$. 
This would be an interesting problem to consider. 
%
% sec6.tex
%
\beginsection 6. Some generalisations

The technique used in~{\refRoTu} to prove Theorem~{\RoTu} gives two results of
a more general nature. Roughly speaking, these results assert the existence of
graphs~$G$ of large girth satisfying~$G\mcarrow H$ for any very sparse
graph~$H$. Given a graph~$H$, let~$m(H)=\max\{e(H')/|H'|\}$, where the maximum
is taken over all subgraphs~$H'\subset H$ of positive order.  Using a simple
`decomposition' result given in~{\refRoTu} (cf.~the proof of Theorem~2
in~{\refRoTu}), and the methods of Sections~2 and~3 above applied to the {\it
non-bipartite\/} Ramanujan graphs $X^{p,q}$ of Lubotzky, Phillips, and
Sarnak~{\refLPS} (so here~$p$ is a quadratic residue modulo~$q$), one may
prove the following result. 

\proclaim Theorem {\GenA}. Let~$t$, $h\geq3$ be given. Then there
exist primes~$p$ and~$q$, a real~$\mu>0$, and an integer~$g\geq3$ such that
if~$G=G_{t,h}=X^{p,q}$, then ({\it i\/})~$g(G)\geq t$ and ({\it
ii\/})~$G\mcarrow H$ for every graph~$H$ with~$m(H)\leq1+\mu$, $g(H)\geq g$,
and~$|H|\leq h$.
\endproclaim

Theorem~{\GenA} above has as an immediate corollary Theorem~{\GenB} below.
For two graphs~$G$ and~$H$, let us write~$G\mcarrow T\!H$ if for
any proper edge-colouring~$\gamma$ of~$G$, there is a subgraph~$H'\subset G$
of~$G$ that is a subdivision of~$H$ and such that~$\gamma$ is injective
on~$E(H')$.

\proclaim Theorem {\GenB}. Let~$t$, $k\geq3$ be given. Then there exist
primes~$p$ and~$q$ such that if~$G=G_{t,k}=X^{p,q}$, then ({\it
i\/})~$g(G)\geq t$ and ({\it ii\/})~$G\mcarrow T\!K^k$.
\endproclaimsquare

Note that this result settles a generalised version of Spencer's original
question. Indeed, when~$k=3$ this theorem asserts the existence of graphs of
arbitrarily large girth that have the property that however they are properly
edge-coloured, we may always find a multicoloured cycle in them.  Moreover,
Theorem~{\GenB} tells us that suitable Ramanujan graphs have this property.
The existence of the graphs~$G_{t,h}$ and~$G_{t,k}$ as above was proved
in~{\refRoTu} by non-constructive means, and no explicit examples of such
graphs were given.  Our aim in this section is to give a sketch of proof for
Theorem~{\GenA}.

We start with some preparation concerning the decomposition result given
in~{\refRoTu}. Let an integer~$s\geq1$ be given. A sequence of
graphs~$(F_k)_0^m$ is an $s$-{\deffont decomposition series\/} for a graph~$H$
if~$K^1=F_0\subset\cdots\subset F_m=H$ and, for all~$1\leq k\leq m$, the
graph~$F_k$ is obtained from~$F_{k-1}$ either by the addition of an isolated
vertex or of a vertex of degree one, or else by the addition of an
$x'$--$y'$~path of order at least~$s$, by joining~$x'$ (respectively~$y'$) to
a vertex~$x\in F_{k-1}$ (respectively~$y\in F_{k-1}$), where~$x$ and~$y$ are
not necessarily distinct.  Thus, more precisely, we either
have~$|F_k|=|F_{k-1}|+1$, $V(F_k)=V(F_{k-1})\cup\{x\}$, and~$d_{F_k}(x)\leq1$,
or else we have~$|F_k|\geq|F_{k-1}|+s$, for all~$w\in W=V(F_k)\setminus
V(F_{k-1})$ we have~$d_{F_k}(w)=2$, and~$W$ induces a path in~$F_k$.

For sparse graphs of large girth, as shown by R\"odl and Tuza~{\refRoTu}, we
have the following simple result on the existence of decomposition series. 

\proclaim Lemma {\decser}. If a graph~$H$ is such that~$m(H)<1+1/(3s-1)$
and~$g(H)\geq s+1$, then~$H$ admits an $s$-decomposition series.
\endproclaimsquare

To prove Theorem~{\GenA}, in addition to Lemma~{\decser} we need a somewhat
cumbersome technical lemma, namely Lemma~{\cues} below. Before we can state
that result, we need to introduce a few definitions and some notation.  Let us
fix a non-bipartite Ramanujan graph~$G=G^n=X^{p,q}$, and recall that
($\dagger$)~the inequality in Lemma~{\Ram}({\it iii\/}) holds for any two
disjoint sets~$U$, $W\subset V(G)$ (cf.~Alon and Spencer~{\refAS}, Chapter~9,
Section~2). Suppose~$\gamma:E(G)\to\N$ is a fixed proper edge-colouring
of~$G$.  Let~$m\geq1$ be fixed, and let~$V=V(G)=V_0\cup\cdots\cup V_m$ be a
partition of~$V$ such that~$n'=|V_1|=\ldots=|V_m|$ is even and~$\lfloor
n/2m\rfloor\leq n'\leq\lfloor n/2m\rfloor+1$. Also, for~$1\leq k\leq m$,
let~$V_k=S_k\cup T_k$ be a partition of~$V_k$ with~$|S_k|=|T_k|$, and
let~$G_k'=G[S_k,T_k]$ be the bipartite graph induced by the vertex
classes~$S_k$ and~$T_k$ in~$G$.  Now let~$\N=C_1\cup\cdots\cup C_m$ be a
partition of~$\N$, and let~$G_k=G_k'[\gamma^{-1}(C_k)]$ ($1\leq k\leq m$).
Now, the argument used in the proof of Lemma~{\splitting} gives that there is
a partition~$(C_k)_1^m$ of~$\N$ such that~$e(G_k)\geq(1/2m)e(G'_k)$ ($1\leq
k\leq m$), provided~$d=p+1$ is at least as large as a constant~$d_0=d_0(m)$
depending only on~$m$. In the sequel, we assume that our partition~$(C_k)_1^m$
is as above. Moreover, from now on we tacitly assume that~$d=p+1$ is large
enough with respect to~$m$. 

\proclaim Lemma {\cues}. Let~$m\geq1$ be fixed. Then there are
constants~$c_i>0$ $(0\leq i\leq3)$ depending only on~$m$ satisfying the
following property. For each~$i\in\{0,1\}$ and~$1\leq k\leq m$, there are
sets~$S_k^{(i)}\subset S_k$, $T_k^{(i)}\subset T_k$, and a vertex~$x_0\in V_0$
such that~$S_k^{(0)}\cap S_k^{(1)}=\emptyset$ and~$T_k^{(0)}\cap
T_k^{(1)}=\emptyset$ $(1\leq k\leq m)$ and such that the following holds.
Let~$J_k^{(i)}=G_k[S_k^{(i)},T_k^{(i)}]$ $(i\in\{0,1\},\,1\leq k\leq m)$.
Then, for all~$1\leq k\leq m$ and~$i\in\{0,1\}$, we have
\item{({\it i\/})}$|S_k^{(i)}|$, $|T_k^{(i)}|\geq r_k=c_1^{m-k}r$,
where~$r\geq c_0n$,
\item{({\it ii\/})}$|\Gamma_G(x_0)\cap S_k^{(i)}|\geq d|S_k^{(i)}|/2n$
and~$|\Gamma_G(x_0)\cap T_k^{(i)}|\geq d|T_k^{(i)}|/2n$,
\item{({\it iii\/})}for all~$k<\ell\leq m$, and~$i_k$, $i_\ell\in\{0,1\}$,
if~$x\in J_k^{(i_k)}$ then~$|\Gamma_G(x)\cap S_\ell^{(i_\ell)}|\geq
d|S_\ell^{(i_\ell)}|/2n$ and~$|\Gamma_G(x)\cap T_\ell^{(i_\ell)}|\geq
d|T_\ell^{(i_\ell)}|/2n$, 
\item{(\it iv\/)}$J_k^{(i)}$ is $(c_2r_k/f,f)$-expanding for all~$0<f\leq
c_3d$. 
\endproclaimsquare

We only briefly describe a proof of Lemma~{\cues}. We start by applying the
`bipartite version' of Szemer\'edi's lemma for subgraphs of pseudo-random
graphs (see~{\refKo}) to the graphs~$G_k\subset G_k'$, with an appropriately
small~$\epsilon=\epsilon(m)>0$. This gives us sets~$S_k'\subset S_k$,
$T_k'\subset T_k$ ($1\leq k\leq m$) with~$|S_k'|=|T_k'|=\Omega(n)$ for all~$k$
and such that~$G_k[S_k',T_k']$ is $(\epsilon,G_k,G_k')$-regular
and~$e(G_k[S_k',T_k'])\geq(1/3m)e(G_k'[S_k',T_k'])$. (For the definition of
these terms, the reader is referred to~{\refKo}.)  We now define the
sets~$S_k^{(i)}$, $T_k^{(i)}$ as required in the lemma by reverse induction
on~$k$, and we define the vertex~$x_0$ last.

Let us first split~$S_m'$ and~$T_m'$ into pairs of sets of cardinality as
equal as possible, say~$S_m'=S_{m,0}\cup S_{m,1}$ and~$T_m'=T_{m,0}\cup
T_{m,1}$. Applying the argument we used in the proof of Lemma~{\Beck}, we may
find suitable sets~$S_m^{(i)}\subset S_{m,i}$, $T_m^{(i)}\subset T_{m,i}$
($i\in\{0,1\}$) as required.  Now we alter the sets~$S_k'$, $T_k'$ ($1\leq
k<m$) to guarantee ({\it iii\/}) in our lemma: we delete from~$S_k'\cup T_k'$
any vertex~$x$ for which~$|\Gamma_G(x)\cap S_m^{(i)}|<d|S_m^{(i)}|/2n$
or~$|\Gamma_G(x)\cap T_m^{(i)}|<d|T_m^{(i)}|/2n$ for some~$i\in\{0,1\}$.
Let~$S_k''\subset S_k'$, $T_k''\subset T_k'$ be the sets we obtain in this
way, and then note that by~($\dagger$) we have~$|S_k''|\geq|S_k'|/2$,
$|T_k''|\geq|T_k'|/2$ ($1\leq k<m$). Moreover, by the
$(\epsilon,G_k,G_k')$-regularity of~$G_k[S_k',T_k']\subset G_k'[S_k',T_k']$,
we have~$e(G_k[S_k'',T_k''])\geq(1/6m)e(G_k'[S_k'',T_k''])$ ($1\leq k<m$).

We now consider~$S_k''$, $T_k''$ ($1\leq k<m$), and by induction find
sets~$S_k^{(i)}$, $T_k^{(i)}$ ($i\in\{0,1\}$, $1\leq i<k$) satisfying~({\it
i\/}), ({\it iii\/}), and~({\it iv\/}) in Lemma~{\cues}. This completes the
definition of the sets~$S_k^{(i)}$, $T_k^{(i)}$. The existence of a suitable
vertex~$x_0\in V_0$ satisfying Lemma~{\cues}({\it ii\/}) follows
from~($\dagger$).  Finally, we note that Theorem~{\GenA} follows from
Lemmas~{\decser} and~{\cues}.

\proofof{{\it Theorem~{\GenA}\/}}. Let~$t$, $h\geq3$ be fixed, and note that
we may clearly assume that~$t\geq4$.  Let~$g=4+3t$ and suppose~$\mu<1/(9t+8)$
is a fixed real. Moreover, let~$p$, $q$ be primes congruent to~$1$ modulo~$4$
with~$p$ a quadratic residue modulo~$q$.  Arguing in the same way as in
Section~4, we see that there are arbitrarily large primes~$p$ and~$q$ as above
satisfying the additional property that~$p^{t/2}\leq q\leq2p^{t/2}$. Let us
fix such a pair~$(p,q)$ with~$p$ large enough with respect to~$h$. From the
properties of~$p$ and~$q$ above, we see that the Ramanujan
graph~$G=G^n=X^{p,q}$ of Lubotzky, Philips, and Sarnak~{\refLPS} is
non-bipartite, has order~$n=q(q^2-1)/2$, has girth~$g(G)\geq t$, and is
$d$-regular with~$d=p+1\geq2^{-4/9}n^{2/3t}$. We claim that~$G$ will do in
Theorem~{\GenA} for the given values of~$t$ and~$h$.

Let~$H$ be a graph of order~$h$ with~$m(H)\leq1+\mu$ and girth~$g(H)\geq g$.
Let~$\gamma:E(G)\to\N$ be a proper edge-colouring of~$G$. We shall show
that~$G$ admits a multicoloured copy of~$H$ with respect to~$\gamma$. To do
so, let~$(F_k)_0^m$ be an $s$-decomposition series for~$H$ with~$s=3t+3$.
Also, fix partitions~$(V_k)_0^m$ and~$(C_k)_1^m$ as in the paragraph before
Lemma~{\cues}, and apply that lemma. Now, the argument used in the proof of
Lemma~{\MainLemma} and Theorem~{\MainRes}, coupled with a simple induction,
successively gives that multicoloured copies of the graphs~$K^1=F_0\subset
F_1\subset\cdots$ are present in~$G$, and hence a multicoloured copy of~$H$
does appear in~$G$, as required. We omit the details.
\endproof

We close with a Ramsey type result. As customary, for graphs~$G$ and~$H$ and
an integer~$r\geq2$, write~$G\to(H)_r$ if in any (not necessarily proper)
edge-colouring of~$G$ with $r$-colours we may find a monochromatic copy
of~$H$. By making use of Szemer\'edi's regularity lemma for subgraphs of
pseudo-random graphs~{\refKo}, one may prove the following result
(cf.~{\refHPhD}). 

\proclaim Theorem {\rbdd}. Let~$r\geq2$ be given. Then there are
constants~$c_0=c_0(r)>0$ and~$p_0=p_0(r)$ such that the following holds.
Let~$p$ and~$q$ be two unequal primes such that~$p$, $q\equiv1\;(\mod 4)$,
$p\leq q^2$, and~$p$ is a square in~$\Z/q\Z$. Let~$t\geq3$ be given.
If~$p\geq p_0$ and~$q\geq q_0=q_0(r,p,t)$, where~$q_0=q_0(r,p,t)$ depends only
on~$r$, $p$, and~$t$, then~$G=G^n=X^{p,q}$ is such that ({\it
i\/})~$e(G)=(p+1)n/2$, ({\it ii\/})~$g(G)\geq t$, and ({\it
iii\/})~$G\to(C^s)_r$ for any integer~$s$ with~$4\log_2n+1\leq s\leq c_0n$.
\endproclaimsquare

This result has a simple consequence concerning multicoloured cycles in
edge-coloured graphs.  Let~$r\geq1$ be given. Let us say that a (not
necessarily proper) edge-colouring~$\gamma:E(G)\to\N$ of a graph~$G$ is
{\deffont$r$-bounded\/} if~$|\gamma^{-1}(\{i\})|\leq r$ for all~$i\in\N$.  Let
us write~$G\rbddarrow H$ if, for any $r$-bounded edge-colouring of~$G$, there
is a multicoloured copy of~$H$ in~$G$. Clearly, if for two graphs~$G$ and~$H$
we have~$G\to(H)_r$, then~$G\rbddarrow H$. Thus, Theorem~{\rbdd} implies that
in $r$-bounded edge-colourings of Ramanujan graphs, we can always find very
long multicoloured cycles. This is of some interest in view of the remark in
the last paragraph of Section~3. For a related result, the reader is referred
to Frieze and Reed~{\refFrieR}, where it is proved that, for some large
constant~$A$, any $r$-bounded edge-colouring of the complete graph~$K^n$
admits a multicoloured Hamilton cycle, where~$r=r(n)=n/A\log n$.  Hahn and
Thomassen~{\refHTho} conjecture that the statement above holds for
some~$r=r(n)=\Omega(n)$.

\finalnotes
Acknowledgements. This work is part of the PhD thesis of the first author, who
worked under the supervision of Dr~B.~Bollob\'as at the University of
Cambridge, and was supported by an NSERC Canada~1967 Science and Engineering
Scholarship. The second author was supported by Churchill College, Cambridge,
where he was a Junior Research Fellow while this work was being done. The
authors are indebted to Drs~B.~Bollob\'as and L.~Babai for their insightful
comments on previous versions of this note.
\endfinalnotes
%
% \shipoutreferences
%
\firstgofalse\refno=0
\beginreferences
\paper[Alon] \Al
            Eigenvalues and expanders
            \Comb\vol6
            83--96, 1986
\paper[AC]  \Al, \Chung
            Explicit construction of linear sized tolerant networks 
            \DM\vol72
            15--19, 1988
\paper[AMb] \Al, Milman, V.D.
            $\lambda_1$, isoperimetric inequalities for graphs %
            and superconcentrators
            \JCTB\vol38
            73--88, 1985
\book[AS]   \Al, \Sp
            The Probabilistic Method
            John Wiley and Sons, Inc., New York~1992, ${\it xiii}+254$pp
\paper[Ba]  Babai, L.
            An anti-Ramsey theorem
            \GC\vol1
            23--28, 1985
\paper[Beck] Beck, J.
            On size Ramsey number of paths, trees, and circuits~I
            \JGT\vol7
            115--129, 1983
\paper[BiBo] Biggs, N.L., Boshier, A.G. 
            Note on the girth of Ramanujan graphs
            \JCTB\vol49
            190--194, 1990
\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[E]   \Er
            Some old and new problems in various branches %
            of combinatorics 
            Cong. Numerantium\vol23
            19--37, 1979
\paper[ERcan]  \Er, Rado, R.
            A combinatorial theorem
            \JLMS\vol25
            249--255, 1950
\paper[FP]  Friedman, J., Pippenger, N.
            Expanding graphs contain all small trees
            \Comb\vol7
            71--76, 1987
\dammit[FrieR] Frieze, A., Reed, B.
            Polychromatic Hamilton cycles, to appear
\paper[HTho] Hahn, G., Thomassen, C.
            Path and cycle sub-Ramsey numbers and %
            an edge-colouring conjecture
            \DM\vol62
            29--33, 1986
\dammit[HPhD] Haxell, P.E.
            {\it Extremal and Ramsey Type Results for Graphs %
            and Hypergraphs\/}, PhD thesis, University of Cambridge, %
            March~1993
\dammit[Ko] Kohayakawa, Y.
            A version of Szemer\'edi's regularity lemma for %
            sparse pseudo-random graphs, manuscript
\dammit[Lef] Lefmann, H.
            On an anti-Ramsey type result, %
            Pre-print~91--023, Universit\"at Bielefeld, 1991
\paper[LPS] Lubotzky, A., Phillips, R., Sarnak, P.
            Ramanujan graphs
            \Comb\vol8
            261--277, 1988
\dammit[Marg] Margulis, G.A.
            Explicit group-theoretical constructions of combinatorial %
            schemes and their application to the design of expanders and %
            superconcentrators, {\it Problemy Peredachi %
            Informatsii\/}~{\bf24} (1988), 51--60 (in Russian), %
            English translation in {\it Problems of Information %
            Transmission\/}~{\bf24} (1988), 39--46 
\dammit[NR] \Ne, \Ro
            Partite construction and Ramsey space systems, in {\it
            Mathematics of Ramsey Theory\/}, Algorithms and %
            Combinatorics~5 (\Ne, \Ro, eds), Springer-Verlag, %
            Berlin~1990, pp.~98--112
\paper[PV]  Pr\"omel, H.J., Voigt, B.
            Canonizing Ramsey theorems for finite graphs and %
            hypergraphs
            \DM\vol54
            49--59, 1985 
\paper[RoTu] \Ro, \Tu
            Rainbow subgraphs in properly edge-coloured graphs
            \RSA\vol3
            175--182, 1992
\dammit[Sz] \Sz
            Regular partitions of graphs, %
            in {\it Probl\`emes en Combinatoire et Th\'eorie des Graphes\/}, %
            Proc. Colloque Inter. CNRS %
            (Bermond, J.-C., Fournier, J.-C., Las Vergnas, M., %
            Sotteau, D., eds), CNRS, Paris~1978, pp.~399--401
\endreferences
\bye
% Local Variables: 
% mode: tex
% TeX-master: t
% End: 
