% A plain TeX file for a 12 page document \input mssymb % % STYLE SECTION % % \magnification=\magstep1 \hsize=5.9truein \raggedbottom \def\today{\ifcase\month \or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \space \number\day, \number\year} % % Time macro % \newcount\hour \newcount\minute \newcount\dummy \dummy=\time \divide \dummy by 60 \hour=\dummy \multiply\dummy by 60 \minute=\time \advance\minute by -\dummy \def\now{\ifnum\minute<10 \number\hour:0\number\minute\else \number\hour:\number\minute\fi} % \parskip=1.28\smallskipamount \parindent=0pt \baselineskip=1.1\normalbaselineskip % Use these for very %\smallskipamount=1.28\smallskipamount % spacy output. Good for \medskipamount=1.28\medskipamount % Good for Combinatorica \bigskipamount=1.28\bigskipamount % %\parskip=1.48\smallskipamount \parindent=0pt %\baselineskip=1.48\normalbaselineskip % Use these for very %\smallskipamount=1.48\smallskipamount % spacy output. Good for %\medskipamount=1.48\medskipamount % Good for Combinatorica %\bigskipamount=1.48\bigskipamount % %\parskip=1.68\smallskipamount \parindent=0pt %\baselineskip=1.68\normalbaselineskip % Use these for very %\smallskipamount=1.68\smallskipamount % spacy output. %\medskipamount=1.68\medskipamount % DOUBLE SPACING %\bigskipamount=1.68\bigskipamount % \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\bscaps=cmcsc10 \font\nineit=cmti9 \font\eightit=cmti8 \font\ninesl=cmsl9 \font\eightsl=cmsl8 %\font\ninemsx=msxm9 \font\eightmsx=msxm8 \font\sixmsx=msxm6 %\font\ninemsy=msym9 \font\eightmsy=msym8 \font\sixmsy=msym6 % 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\msxfam=\ninemsx \scriptfont\msxfam=\sixmsx %\scriptscriptfont\msxfam=\fivemsx %\textfont\msyfam=\ninemsy \scriptfont\msyfam=\sixmsy %\scriptscriptfont\msyfam=\fivemsy %\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\msxfam=\eightmsx \scriptfont\msxfam=\sixmsx \scriptscriptfont\msxfam=\fivemsx \textfont\msyfam=\eightmsy \scriptfont\msyfam=\sixmsy \scriptscriptfont\msyfam=\fivemsy %\tt\ttglue=.5em plus.25em minus.15em \normalbaselineskip=10pt \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}% \let\sc=\sixrm%\let\big=\eightbig \normalbaselines\rm} \def\enddiscard{} \long\def\discard#1\enddiscard{} % % further maths macros % \def\N{{\Bbb N}} \def\Z{{\Bbb Z}} \def\R{{\Bbb R}} \def\im{\mathop{\rm im}\nolimits} \def\({\left(} \def\){\right)} \def\[{\left[} \def\]{\right]} \def\bl{\left\{} \def\br{\right\}} \def\setof#1{\left\{#1\right\}} \def\sizeof#1{\left|#1\right|} \def\comp{^{\rm c}} \def\superset{\supset} \def\av{{\bar {\rm d}}} \def\gcd{{\rm gcd}} % % % Font definitions for use in document % \font\titlefont=cmbx12 scaled \magstep2 \font\sectionfont=cmbx12 scaled \magstep1 %\font\titlefont=cmcsc10 scaled \magstep4 %\font\sectionfont=cmcsc10 scaled \magstep2 \def\authorfont{\bscaps} % font for author's name \def\rauthorfont{\bscaps} % font for authors in references \def\addressfont{\it} % font for address \font\hifont=cmssi10 % font for highlighting \font\bighifont=cmssi10 scaled \magstep2 % font for title highlighting \def\prcfont{\bf} % font for theorems %\def\prcfont{\bscaps} % font for theorems for ps % % \def\version [#1]{\headline{\hifont\hfill#1 --- \now\ \ \today}} \def\title#1{\null\vglue2truecm{{\pretolerance=10000\centerline{\titlefont #1}}}\bigskip} \def\begintitle{\pretolerance=10000\null\vglue2truecm\titlefont} \def\endtitle{\pretolerance=100\rm\bigskip} \def\author#1{{\authorfont\vglue.25truecm\centerline{#1}}} \def\sponsor{\footnote*{{\eightpoint Supported by }}} \def\endaddress{\par\endgroup} %\def\address#1\endaddress{\medskip\begingroup % \noindent\raggedright\addressfont#1\endaddress} \def\address{\medskip\begingroup \noindent} %\baselineskip=9pt\eightpoint use eightpoint except for submitting \def\DPMMS{{\addressfont\centerline{Department of Pure Mathematics and Mathematical Statistics,} \centerline{University of Cambridge, 16 Mill Lane, Cambridge,} \centerline{CB2~1SB, England.}}} \def\UMEA{{\addressfont\centerline{Department of Mathematics} \centerline{Ume\aa\ University, S--901 87 Ume\aa, Sweden}}} \def\endabstract{\par\endgroup} \def\abstract{\vglue2.3truecm\begingroup \noindent{\bf Abstract.\enspace}\ignorespaces\eightrm} %\ninepoint use ninepoint except for submitting \def\endfinalnotes{\par\endgroup} \def\finalnotes#1.{\bigbreak\begingroup \eightpoint\noindent{\bf #1.\enspace}\ignorespaces} \def\leaderfill{\leaders\hbox to 1em{\hss.\hss}\hfill} \def\acknowledge{\vskip 1truein\goodbreak\vskip- .25truein\leftline{\titlefont Acknowledgements}} \newcount\secno \secno=0 \newcount\resno \resno=0 \newcount\aresno \aresno=0 \newcount\diagno \diagno=0 % \def\longtitle#1{\halign{\quad##\hfill\cr \kern-1em#1\cr\cr}} % \outer\def\beginsection [#1] #2\par{\vskip 1truein\allowbreak \vskip -1truein\bigskip \global\advance\secno by 1 \message{\number\secno.\ #2} {\leftline{\sectionfont \S\number\secno.\ #2} \nobreak\smallskip\vskip-\parskip} \global\expandafter\edef\csname csec#1\endcsname{{\number\secno} #2} \global\expandafter\edef\csname sec#1\endcsname{Section~{\number\secno}\ } \global\expandafter\edef\csname psec#1\endcsname{\number\count0}} % \def\final{\vskip 2truein\bigbreak\vskip-2truein\leftline{\sectionfont Concluding remarks}} % \outer\def\beginsubsection#1\par{\bigskip \message{#1}\leftline{\prcfont#1}\nobreak\smallskip\vskip-\parskip \noindent} % \def\thesbreak{\vskip 2truein\goodbreak\vskip-2 truein} \def\vgbreak{\vfil\goodbreak\vfilneg} \outer\def\proclaim #1. {\message{#1 }\medbreak \noindent{\prcfont#1.\enspace}\bgroup\ignorespaces} \def\endproclaim{\par\egroup\ifdim\lastskip<\medskipamount \removelastskip\penalty1000\medskip\fi} \outer\def\endproclaimsquare{{\unskip\nobreak\hfil\penalty50 \hskip2em\hbox{}\nobreak\hfil\sqr \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106. \egroup\ifdim\lastskip<\bigskipamount\removelastskip\penalty- 10\bigskip\fi} \def\endclaim{\par\ifdim\lastskip<\smallskipamount \removelastskip\penalty20\smallskip\fi} \long\def\claim{\smallbreak \noindent{\prcfont Claim.\enspace}\ignorespaces} \def\endcase{\par\ifdim\lastskip<\smallskipamount \removelastskip\penalty3000\smallskip\fi} \def\case#1.{\smallbreak \noindent{\prcfont Case\/} #1.\enspace\ignorespaces} \def\endcasebody{\par\ifdim\lastskip<\smallskipamount \removelastskip\penalty-20\smallskip\fi} \def\casebody{\noindent\ignorespaces} \def\sqr{\ifmmode\square\else{$\square$}\fi} \def\square{\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\endproof{{\unskip\nobreak\hfil\penalty50 \hskip2em\hbox{}\nobreak\hfil\sqr \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106. {\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}} \outer\def\endproofnosquare{% \ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi} \outer\def\proof{% %\ifdim\lastskip<\medskipamount\removelastskip\penalty1000\medskip\fi \medbreak \noindent{\prcfont Proof.\enspace}\ignorespaces} \outer\def\proofof#1{% %\ifdim\lastskip<\medskipamount\removelastskip\penalty60\medskip\fi \medbreak \noindent{\prcfont Proof of\/ #1}\enspace\ignorespaces} \def\ititem(#1){\item{({\it#1})}} \def\ititemnohangindent(#1){\par\textindent{({\it#1\/})}} \def\defin{{\prcfont Definition }} % % Macros for references % \newif\iffirstgo \def\scanreferences{\firstgotrue\refno=0\beginreferences} \def\shipoutreferences{\firstgofalse\refno=0\beginreferences} \def\endreferences{\par\endgroup} \outer\def\beginreferences {\begingroup\iffirstgo\else\pretolerance=1000\tolerance=3000 \raggedright\frenchspacing\vskip 1truein\goodbreak\vskip-.25truein \global\expandafter\edef\csname prefs\endcsname{\number\count0} \vskip0pt plus.3\vsize\penalty-150\vskip0pt plus-.3\vsize \bigskip\vskip\parskip\message{References} \leftline{\titlefont References} \nobreak\smallskip\ninepoint\fi\obeylines} % Journals \def\BLMS{Bull. London Math. Soc.} \def\JLMS{J. London Math. Soc.} \def\JCT{J. Comb. Theory} \def\JCTA{J. Comb. Theory Ser. A} \def\JCTB{J. Comb. Theory Ser. B} \def\Comb{Combinatorica} \def\AI{Acta Informatica} \def\AMASH{Acta Math. Sci. Acad. Hung.} \def\SSMH{Stud. Sci. Math. Hung.} \def\EJC{Europ. J. Comb.} \def\GC{Graphs and Combinatorics} \def\IJM{Israel J. Math.} \def\ML{Mat. Lapok} \def\Net{Networks} \def\DM{Discrete Math.} \def\ADM{Ann. Discrete Math.} \def\SIAM{SIAM J.Disc Math} \def\TAMS{Trans. Amer. Math. Soc.} \def\QJM{Quart. J. Math} % Authors \def\Aj{Ajtai, M.} \def\Al{Alon, N.} \def\Bar{B\'ar\'any, I.} \def\Bl{Blum, A.} \def\BB{Bollob\'as, B.} \def\Bo{Bondy, J.A.} \def\Bu{Burr, S.A.} \def\Chung{Chung, F.R.K.} \def\Deza{Deza, M.} \def\me{Denley, T.M.J.} \def\Er{Erd\H os, P.} \def\Fa{Faudree, R.J.} \def\Fr{Frankl, P.} \def\Fu{F\"uredi, Z.} \def\Ger{Gerencs\'er, L.} \def\Gya{Gy\'arf\'as, A.} \def\Gra{Graham, R.L.} \def\Gri{Griggs, J.R.} \def\Ha{Hal\' asz, G.} \def\Kl{Kleitman, D.J.} \def\Ko{Chao Ko} \def\Kom{Koml\'os, J.} \def\Le{Leader, I.} \def\Lem{Lemke, P.} \def\Lo{Lov\'asz, L.} \def\Moews{Moews, D.} \def\Mo{Monien, B.} \def\Mi{Mizuno, H.} \def\Ne{Ne\v set\v ril, J.} \def\Po{Poljak, S.} \def\Ra{Rado, R.} \def\Ram{Ramsey, F.P.} \def\Ro{R\"odl, V.} \def\Ros{Rosta, V.} \def\Rot{Rothschild, B.L.} \def\Sa{Sato, I.} \def\Sc{Schelp, R.H.} \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\Spe{Speckenmeyer, E.} \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 #5 #6 #7 {\global\advance\refno by1% \iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno] }% \else\filbreak\smallskip\item{[\number\refno]} % {\rauthorfont #2}, {\it #3}, #4~{\prcfont #5} (#7), \hbox{#6}.\fi}% \global\def\proceedings[#1] #2 #3 #4 #5 {\global\advance\refno by1% \iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno] }% \else\filbreak\smallskip\item{[\number\refno]} {\rauthorfont #2}, {\it #3}, in {``#4''}, #5.\fi}% \global\def\book[#1] #2 #3 #4 #5 {\global\advance\refno by1% \iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno] }% \else\filbreak\smallskip\item{[\number\refno]} {\rauthorfont #2}, {\it #3}, #4, #5.\fi}% \global\def\preprint[#1] #2 #3 #4 {\global\advance\refno by1% \iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno] }% \else\smallskip\item{[\number\refno]} {\rauthorfont #2}, {\it #3}, #4.\fi}% % \global\def\privatecomm[#1] #2 {\global\advance \refno by1% \iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno] }% \else\smallskip\item{[\number\refno]} {\rauthorfont #2}, {\it private communication}.\fi}% % \global\def\unpublished[#1] #2 {\global\advance \refno by1% \iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno] }% \else\smallskip\item{[\number\refno]} {\rauthorfont #2}, {\it unpublished}.\fi}% \global\def\dammit[#1] #2 #3 {\global\advance \refno by1% \iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno] }% \else\smallskip\item{[\number\refno]} {\rauthorfont #2}, {\it #3}.\fi}% \endgroup % % results macros % \def\aletter{\ifcase\aresno \or A\or B\or C\or D\or E\or F\or G \or H\or I\or J\or K\or L\or M\or N\or O\or P\or Q\or R\or S\or T\or U\or V\or W\or X\or Y\or Z\fi} \begingroup \long\global\def\Theorem [#1] {\global\advance\resno by1% \global\expandafter\edef\csname res#1\endcsname{Theorem~{\number\resno} } {\message{Theorem #1-\number\resno } \medbreak\allowbreak {\prcfont Theorem~{\number\resno }\enspace} %\prcfont Theorem~{#1}\enspace} \bgroup\sl\ignorespaces}}% \global\def\Lemma [#1] {\global\advance\resno by1% \global\expandafter\edef\csname res#1\endcsname{Lemma~{\number\resno} }{ \message{Lemma #1-\number\resno } \medbreak\allowbreak {\prcfont Lemma~{\number\resno }\enspace} %\prcfont Lemma~{#1}\enspace} \bgroup\sl\ignorespaces}}% \global\def\Corollary [#1] {\global\advance\resno by1% \global\expandafter\edef\csname res#1\endcsname{Corollary~{\number\resno} }{ \message{Corollary #1-\number\resno } \medbreak\allowbreak {\prcfont Corollary~{\number\resno\enspace} %\prcfont Corollary~{#1} \enspace}\bgroup\sl\ignorespaces}}% \long\global\def\ATheorem [#1] {\global\advance\aresno by1% \global\expandafter\edef\csname ares#1\endcsname{Theorem~{\aletter} }{ \message{Author--Theorem #1-\aletter } \medbreak\allowbreak {\prcfont Theorem~{\aletter}\enspace} %\prcfont Theorem~{#1}\enspace} \bgroup\sl\ignorespaces}}% \endgroup % % Macros for diagrams % \global\def\readdiag [#1] #2 {\global\advance\diagno by1% \topinsert\input diag#1 \centerline{Figure~{\number\diagno}-- #2} \endinsert %{\message{Diagram #1-{\number\diagno}}} } % % START OF PAPER % % \scanreferences % \paper [AKSI] {\Aj,\Kom \thinspace and \Sz} {A note on Ramsey Numbers} \JCTA {29} {354--360} 1980 \paper [AKSII] {\Aj,\Kom \thinspace and \Sz} {A dense infinite Sidon sequence} \EJC {2} {1--11} 1981 \proceedings [Bl] {\Bl} {An $\hbox{O}(n^{.4})$--approximation algorithm for 3--colouring ( and improved approximation algorithms for $k$--colouring} {Proceedings of the 21$^{st}$ Annual ACM Symposium on the Theory of Computing} {Seattle, May 1989, pp 535--542} \proceedings [Bli] {\Bl} {Some tools for approximate 3--colouring} {Proceedings of the 31$^{st}$ Annual Symposium on the Foundations of Computer Science} {pp 554--562} \paper [Gri] \Gri {An upper bound on the Ramsey number R(3,k)} \JCTB {35} {145--153} 1983 \paper [MoS] {\Mo \thinspace and \Spe} {Ramsey numbers and an approximation algorithm for the vertex cover problem} \AI {22} {115--123} 1985 \paper [ShI] {\Sh} {A note on the independence number of triangle--free graphs} \DM {46} {83--87} 1983 \paper [ShII] {\Sh} {A note on the independence number of triangle--free graphs, II} \JCTB {53} {300--307} 1991 \endreferences % \font\smcp=cmcsc8 \headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 1 (1994), \#R9\hfill\folio} \fi} % % \begintitle \centerline{The independence number of} \centerline{graphs with large odd girth} \endtitle \author{Tristan Denley\footnote*{\eightrm Correspondence to Tristan Denley, Matematiska institutionen, Ume{\aa} universitet, Ume{\aa}, Sweden}\footnote{}{\eightrm Email to tristan@abel.math.umu.se}} \address\DPMMS\endaddress \bigskip \centerline{Submitted: August 6, 1994; Accepted: September 17, 1994.} \bigskip \abstract Let $G$ be an $r$-regular graph of order $n$ and independence number $\alpha(G)$. We show that if $G$ has odd girth $2k+3$ then $\alpha(G)\geq n^{1-1/k}r^{1/k}$. We also prove similar results for graphs which are not regular. Using these results we improve on the lower bound of Monien and Speckenmeyer, for the independence number of a graph of order $n$ and odd girth $2k+3$. \endabstract \medskip {\bf AMS Subject Classification.} 05C15 \bigskip \beginsection [inda] {Introduction} Let $G$ be a triangle--free graph of order $n$ with average degree $d$, and independence number $\alpha(G)$. There has been great interest in finding good lower bounds for $\alpha(G)$ in terms of $d$, and producing polynomial--time algorithms which find large independent sets of $G$. In \refAKSI and \refAKSII Ajtai, Koml\'os and Szemer\'edi made a breakthrough in this area when they provided a polynomial algorithm to find an independent set of size at least $$\alpha(G)\geq {n\log d \over 100d}\;.$$ A little later this algorithm was sharpened by Griggs in \refGri, improving the constant from $100^{-1}$ to $2.4^{-1}$. Shearer, in \refShII, improved this bound still further to give that $$\alpha(G)\geq n\biggl[{{d(\log d)-d+1}\over (d-1)^2}\biggr]\;.$$ In \refShII besides extending this result to take the degree sequence of the graph into account Shearer also considered what could be said for graphs of larger odd girth. He proved the following theorem. \proclaim Theorem A. Let $G$ be a graph of order $n$ with degree sequence $d_1,d_2,\dots,d_n$. Suppose that $G$ contains no $3$ or $5$ cycles. Let $n_{11}$ be the number of pairs of adjacent vertices of degree 1 in $G$. Let $f(0)=1$, $f(1)=4/7$ and $f(d)=[1+(d^2-d)f(d-1)](d^2+1)^{-1}$ when $d\geq 2$. Then $$\alpha(G)\geq \sum_{i=1}^n f(d_i)-n_{11}/7\;.$$ \endproclaimsquare The results of this paper are designed to deal with the case when the average degree of the graph is large. We shall prove that an $r$-regular graph without 3 and 5 cycles has an independence number of at least $$\alpha(G)\geq\sqrt{{nr\over 6}}\;.$$ Indeed we shall provide a polynomial--time algorithm to produce such a set of independent vertices. More generally,we shall show that an $r$-regular graph with odd girth $2k+3$ has an independent set of size at least $$\alpha(G)\geq c_kn^{1-1/k}\;r^{1/k}\;.$$ This technique can also be used to give new bounds for the independence number of general graphs of a given odd girth. We shall prove some similar bounds to those we prove for regular graphs in terms of a measure of the concentration of edges. Monien and Speckenmeyer in \refMoS investigated the special Ramsey number $r_k(q)$, the largest number of vertices in a graph with odd girth at least $2k+3$, but not containing an independent set of size $q+1$. They showed that $$r_k(q)\leq {k\over k+1}q^{k+1\over k}+{k\over k+2}q\;.$$ Combining our new bound with that of Shearer we show a new bound for the Ramsey number $r_k(q)$ $$r_k(q)\leq \biggl({k\over \ln q}\biggr)^{1\over k}q^{k+1\over k}$$ improving the previous bound provided $q$ is large. \beginsection [indb] {The independence number of regular graphs} In this section we shall introduce the basic algorithmic method we shall use find large independent sets in graphs with large odd girth at. To illustrate the ideas behind this algorithm we shall first prove our results for graphs of odd girth at least 7. Dealing with graphs with larger odd girth will simply require a generalisation of this argument. \Theorem [indBi] Let $G$ be a graph of order $n$ containing containing no 3 or 5 cycles with average degree $\av (G)$ and minimal degree $\delta\geq 2\av(G) /3$. Then $$\alpha (G)\geq {1\over{\sqrt 2}}\sqrt{n\biggl(\delta-{2\av(G)\over 3}\biggr)}$$ and there is a polynomial--time algorithm that finds an independent set of at least this size. \endproclaim \proof Let $$m={1\over{2\sqrt{2}}}\sqrt{n\biggl(\delta -{2\over 3}\av (G)\biggr)^{-1}}$$ We begin by trying to greedy--colour the vertices of $G$ with $m$ colours. In other words we take the vertices one at a time and for each vertex use the smallest available colour. If no colour is available we ignore that vertex and proceed to the next. Firstly suppose that this greedy colouring colours at least $n/4$ vertices. Then, clearly, one of the colour classes will have size at least $${n\over 4m}= {1\over {\sqrt2}}\sqrt{n\biggl(\delta-{2\av(G)\over 3}\biggr)}$$ and we have an independent set to satisfy the theorem. Suppose then that we are not so successful and that $g^\prime\geq 3n/4$ vertices remain uncoloured. Let $A_1,A_2,\dots, A_m$ be the greedy colour classes. Consider the following algorithm {\prcfont SHUFFLE($c$)} for a real parameter $c$. \bigbreak {\prcfont Algorithm: SHUFFLE($c$)} {\parindent=.2truein \item{$\bullet$}$\displaystyle{V(G^\prime)=V(G)\backslash \bigcup_{i=1}^m A_i}$; \item{$\bullet$}Choose $v\in V(G^\prime)$; \item{$\bullet$}Let $I=\Gamma_{G^\prime}(v)$; \item{$\bullet$}Let $N_i(v)=\Gamma_{G}(I)\cap A_i$ for $i=1,\dots,m$; \item{$\bullet$}If there is an $i$ for which $|I|>|N_i(v)|$ then $A_i=A_i\backslash N_i(v)\cup I$; \item{$\bullet$} Repeat until $\sizeof{\bigcup_{i=1}^m A_i}\geq c$ or until every vertex of $G^\prime$ has been chosen since the last time $G^\prime$ changed.} \bigskip As usual set $\Gamma_G(I)=\{v:vi\in E(G) \hbox{ for some }i\in I\}$. Notice that since $I$ is the neighbourhood of a vertex and $G$ is triangle free, $I$ is an independent set. Thus each $A_i$ remains an independent set throughout the algorithm. We apply {\prcfont SHUFFLE}$(n/4)$ to the graph. Consider the situation when the algorithm stops. Either the greedy--colour classes $A_1,A_2,\dots, A_m$ comprise at least $n/4$ vertices and we may argue as before, or for any uncoloured vertex $v\in V(G^\prime)$ $$|N_i(v)|\geq|\Gamma_{G^\prime}(v)|\qquad\hbox{for }1\leq i\leq m\;.$$ Suppose the latter holds. Then, given a vertex $v\in V(G^\prime)$, certainly each $N_i(v)$ is an independent set, since each is a subset of a colour class, but in fact $\bigcup_{i=1}^m N_i(v)$ is an independent set. To prove this we need only show that there can be no edges between a vertex of $N_i(v)$ and $N_j(v)$ for $i\neq j$. Suppose that we have such an edge $ab$ for $a\in N_i(v)$ and $b\in N_j(v)$. Let $I=\Gamma_{G^\prime}(v)$ and consider $\Gamma_G(a)\cap \Gamma_G(b)\cap I$. Firstly suppose that $\Gamma_G(a)\cap \Gamma_G(b)\cap I\neq\emptyset$, containing a vertex, $c$ say. Then vertices $a,b,c$ form a triangle in $G$, contradicting the odd girth of $G$. Otherwise, since by construction $I_{G}(a)\cap I$ and $I_{G}(b)\cap I$ are non--empty, there exist distinct vertices $c\in I_{G}(a)\cap I$ and $d\in I_{G}(b)\cap I$. Then $a,c,v,d,b$ form a 5-cycle in $G$, giving the required contradiction. Now, if we choose a vertex $v$ of maximal degree in $G^\prime$, we certainly have $|\Gamma_{G^\prime} (v)|\geq \av(G^\prime)$, and since $|N_i(v)|\geq \sizeof{\Gamma_{G^\prime} (v)}\geq \av(G^\prime)$ we have that $$\biggl|\bigcup_{i=1}^m N_i(v)\biggr|\geq m\av(G^\prime)\;.$$ Hence the algorithm is guaranteed to find an independent set of size at least $$\min\biggl\{{1\over{\sqrt 2}}\sqrt{n(\delta-{2\av(G)\over 3})}, m\av(G^\prime)\biggr\}\;.$$ It remains only to show that $\av(G^\prime)$ cannot be too small. We do this with a simple counting argument. Let $H^\prime=G\backslash G^\prime$ and let us count the number of edges in $G$ $e(G)$. Then we see that $$\eqalignno{ e(G)&={n\av(G)\over2}\geq {{(n-g^\prime)\av(H^\prime)}\over 2} +g^\prime \delta -{g^\prime\av(G^\prime)\over 2}\;.\cr \noalign{\hbox{Thus, rearranging this inequality we have}} \av(G^\prime)&\geq 2\delta+{{(n-g^\prime)}\over g^\prime}\av(H^\prime) -{n\over g^\prime}\av(G)\cr &\geq 2\delta-{n\over g^\prime}\av(G)\;.\cr \noalign{\hbox{The right hand side of this inequality is increasing with $g^\prime$. Hence, since $g^\prime\geq 3n/4$,}} \av(G^\prime)&\geq 2\delta-{4\av(G)\over 3}\cr \noalign{\hbox{and so using this bound we see that}} m\av(G)&\geq {1\over{\sqrt 2}}\sqrt{n\biggl(\delta -{2\av(G)\over 3}\biggr)}\;.\cr}$$ \endproof Thus \resindBi shows that provided the minimal degree is not too small, there is a large independent set in the graph. In particular, we may apply this result to the case when $G$ is a regular graph. \Theorem [indBii] Let $G$ be an $r$--regular graph of order $n$ with no 3 or 5 cycles. Then $$\alpha (G)\geq \sqrt{{nr\over 6}}\;.$$ \endproclaimsquare Using a similar technique, but applying the algorithm {\prcfont SHUFFLE} recursively we can extend \resindBi to deal with graphs known to have larger odd girth. \Theorem [indBiva] Let $G$ be a graph of order $n$ with odd girth $2k+3$ ($k\geq 2$) and minimal degree $\displaystyle{\delta(G)\geq {2\av (G)\over 3}}$. Then $$\alpha (G)\geq \biggl({n\over 4(k-1)}\biggr)^{k-1\over k}\biggl(2\delta-{4\av(G)\over 3}\biggr)^{1\over k}\;.$$ \endproclaim \proof To construct our independent set we mimic the proof of \resindBi, but this time we choose $$m=\Biggl( {n\over {8(k-1)}}\biggl(\delta -{2\av (G)\over 3}\biggr)^{-1}\Biggr) ^{1\over k}\;.$$ Firstly let us greedily colour the vertices of $G$ just as we did in \resindBi but this time with $(k-1)m$ colours. Clearly if any $sm$ colour classes together contain at least $sn/4(k-1)$ vertices for some $1\leq s\leq (k-1)$ then immediately we have a colour class of size at least $${n\over 4(k-1)m}=\biggl({n\over 4(k-1)}\biggr)^{k-1\over k}\biggl(2\delta-{4\av(G)\over 3}\biggr)^{1\over k}$$ as required. If not then, as before let, $A_1,A_2,\dots , A_{(k-1)m}$ be the greedy--colour classes. For $x,y\in V(G)$ let $d_G(x,y)$ be the usual graph--distance, the minimum number of edges in a path joining $x$ to $y$ in $G$. For each integer $1\leq s\leq (k-1)$ and real $c$ we define a new algorithm similar to {\prcfont SHUFFLE}. \bigskip \goodbreak {\prcfont Algorithm: SHUFFLE}($c,s$) {\parindent=.2truein \item{$\bullet$} Let $\displaystyle{V(G_s^\prime) =V(G)\backslash\bigcup_{i=1}^{sm} A_i}$ \item{$\bullet$}Choose $v\in V(G_s^\prime)$ \item{$\bullet$}Let $I(v)=\{u;d_{G_s^\prime}(u,v)=k-s\}$ \item{$\bullet$}Let $N^s_i(v)=\Gamma_G(I(v))\cap A_i\qquad\hbox{for } (s-1)m+1\leq i\leq sm$ \item{$\bullet$}If there is some $(s-1)m+1\leq j\leq sm$ for which $|I(v)|>|N^s_j(v)|$ then let $A_i=A_i\backslash N^s_j(v)\cup~I(v)$ \item{$\bullet$}Repeat from the beginning until $\sizeof{\bigcup_{i=1}^{sm} A_i}\geq c$ or until each vertex of $G_s^\prime$ has been chosen since the last time $G_s^\prime$ changed.} \medskip Now let us show that, just as our neighbourhoods in {\prcfont SHUFFLE} form a large independent set, here $\displaystyle{\bigcup_{i=(s-1)m+1}^{sm} N^s_i(v)}$ is an independent set. To do this, as before we show that there can be no edge between a vertex $a$ of $N_i^s$ and a vertex $b$ of $N_j^s$, $i\neq j$. Clearly $d_G(v,a)=d_G(v,b)=k-s+1$. Thus consider paths of minimal length joining $a$ and $b$ to $v$, and let $p$ be the vertex furthest from $v$ at which these paths intersect (certainly since they each pass through $v$ there is some intersection). By the minimality of the paths we must have $1\leq d_G(a,p)=d_G(b,p)\leq k-s+1$. Thus if $ab\in E(G)$ $a\dots p\dots b$ forms a cycle of length $3\leq 2d_G(a,p)+1\leq 2k+1$ contradicting the odd girth of $G$. Indeed similarly to the original {\prcfont SHUFFLE} algorithm, on completion the new algorithm {\prcfont SHUFFLE}($c,s$) either produces a greedy--colouring of at least $c$ vertices with $sm$ colours, or ensures that for any vertex $v\in G_{s}^\prime$ $|N_i^s|\geq |I(v)|$ for each $(s-1)m+1\leq i\leq sm$. Let us now define the following algorithm which uses {\prcfont SHUFFLE}($c,s$): \bigskip\goodbreak {\prcfont Algorithm: SHUFFLE*($c$)} {\parindent=.2truein \item{$\bullet$}do $i=k-1$ to $1$ \item{$\bullet$}do $j=i$ to $k-1$ \item{$\bullet$}{\prcfont SHUFFLE}($jc,j$) \item{$\bullet$}continue} \medskip Let us apply {\prcfont SHUFFLE*}($n/(4k-4)$) to $G$. Then on completion either some collection of $sm$ colour classes will contain at least $sn/(4k-4)$ vertices ( for some $1\leq s\leq (k-1)$) and we immediately have a large independent set, or at least $n-{(k-1)n\over 4(k-1)}={3n\over 4}$ vertices remain uncoloured, thus $\sizeof{V(G_{(k-1)}^\prime)}\geq 3n/4$, and for any uncoloured vertex $v\in G_{(k-1)}^\prime$ $$\sum_{i=(s-1)m+1}^{sm}|N^s_i(v)|\geq m^{(k-s)}|\Gamma_{G_{k-1}^\prime}(v)|\qquad 1\leq s \leq (k-1)\;.$$ Now if we choose $v$ to be a vertex of $V(G^\prime_{k-1})$ with degree at least $\av( G_{(k-1)}^\prime)$ then $\bigcup_{i=1}^m N_i^1(v)$ is an independent set of size $$\sum_{i=1}^m|N^1_i(v)|\geq m^{(k-1)}\av(G_{(k-1)}^\prime)\;.$$ Thus the algorithm guarantees to find an independent set of size $$\min\Biggl\{{n\over 4(k-1)m}, m^{k-1}\av(G_{(k-1)}^\prime)\Biggr\}\;.$$ It remains only to reapply the argument used in the proof of \resindBi to show that $$\av (G_{(k-1)} ^\prime)\geq 2\delta(G)-{4\av (G)\over 3}$$ and hence that we have an independent set of size $$\biggl({n\over 4(k-1)}\biggr)^{k-1\over k}\biggl(2\delta-{4\av(G)\over 3}\biggr)^{1\over k}\;.$$ \endproof Applying this bound when the graph is $r$-regular graph, we immediately have an analogous result to \resindBii. \Theorem [indBivb] Let $G$ be an $r$-regular graph of order $n$ and odd girth $2k+3$ ($k\geq 2$). Then $$\alpha(G)\geq c_k\;r^{1/k}\; n^{1-1/k}$$ where $$c_k=\left({2\over 3}\right)^{1/k} \left(4(k-1)\right)^{-(k-1)/k}\;.$$ \endproclaimsquare \beginsection [indc] {Further independence results} The use of the method of \secindb is not solely limited to graphs which are almost regular. In the non--regular case we can still find bounds for the independence number in terms of the odd girth, but instead of the average degree of the graph we have to use another measure of the concentration of edges. \Theorem [indBiv] Let $G$ be a graph of order $n$ with odd girth at least $2k+3$ ($k\geq 2$), and let $$\eqalignno{ \Delta_0&=\min\{\Delta(H): H\subset G, |V(H)|\geq n/k\}\cr \noalign{\hbox {and }} \bar d_0&=\min\{\av(H): H\subset G, |V(H)|\geq n/k\}\;.\cr}$$ Then $$\alpha(G)\geq\max\Biggl\{{{n\log {\bar d_0}}\over{2.4k{\bar d_0}}},\biggl({n\over k}\biggr)^{1- {1/k}}\Delta_0^{1/k} \Biggr\}\;.$$ \endproclaim \proof Firstly as before we can produce an independent set of size at least $${{n\log\bar d_0}\over{2.4k\bar d_0}}$$ by applying the Griggs' algorithm to a subgraph $H$ which achieves $\bar d_0$ as its average degree. To produce an independent set of the other size we mimic the proof of \resindBiva but this time we choose $$m=\biggl({n\over{k\Delta_0}}\biggr)^{1\over k}\;.$$ Let us colour the vertices of $G$ with $(k-1)m$ colours. Clearly if any $sm$ colour classes together contain at least $sn/k$ vertices ($1\leq s\leq (k-1)$) then immediately we have a colour class of size at least $${n\over km}=\biggl({n\over k}\biggr)^{1- {1\over k}}\Delta_0^{1\over k}\;.$$ If not, then as before let $A_1,A_2,\dots , A_{(k-1)m}$ be the greedy--colour classes. Let us now apply {\prcfont SHUFFLE*}($n/k$). When the algorithm stops, either one of the colour classes provides us with the large independent set we desire or for any uncoloured vertex $v\in G_{(k-1)}^\prime$ we have $$\sum_{i=(s-1)m+1}^{sm}|N^s_i(v)|\geq m^{(k-s)}|\Gamma_{G_{k-1}^\prime}(v)|\qquad 1\leq s \leq (k-1)\;.$$ Now since, $|V(G_{(k-1)}^\prime)|\geq n/k$, by definition of $\Delta_0$ we must be able to choose a $v$ so that $|\Gamma_{G_{(k-1)}^\prime}(v)|\geq\Delta_0$ and for this choice we have that $\bigcup_{i=1}^m N_i^1(v)$ is an independent set of size $$\sum_{i=1}^m|N^1_i(v)|\geq m^{(k-1)}\Delta_0=\biggl({n\over k}\biggr)^{1-{1 \over k}}\Delta_0^{1\over k}\;.$$ \endproof In particular, when $k=2$ and the graph has no 3 or 5 cycles we have an analogous result to \resindBii and an extension of Shearer's result, Theorem~A. \Theorem [indBiii] Let $G$ be a graph of order $n$ having no 3 or 5 cycle, and let $$\eqalignno{ \Delta_0&=\min\biggl\{\Delta(H): H\subset G, |V(H)|\geq n/2\biggr\}\cr \noalign{\hbox{and}} \bar d_0&=\min\biggl\{\av(H): H\subset G, |V(H)|\geq n/2\biggr\}\;.\cr \noalign{\hbox{Then}} \alpha(G)&\geq \max\Biggl\{{{n\log {\bar d_0}}\over{4.8{\bar d_0}}},\sqrt{n{\Delta_0}\over 2}\Biggr\}\;.\cr }$$ \endproclaim These results lead directly to a general lower bound for the the independence number of a graph in terms of its order and odd girth simply by minimising the bounds in \resindBiv\llap{.} \Corollary [indBv] Let $G$ be a graph of order $n$ with odd girth at least $2k+3$ ($k\geq 2$). Then $$\alpha(G)\geq \biggl({n\over k}\biggr)^{k\over k+1} (\log n)^{1\over k+1}\;.$$ \endproclaimsquare Looking at the problem the other way round, Monien and Speckenmeyer in \refMoS proved a bound for the Ramsey number $r_k(q)$, the largest number of vertices in a graph with odd girth $2k+3$ and independence number at most $q$. Monien and Speckenmeyer showed that $$r_k(q)\leq {k\over k+1}q^{k+1\over k}+{k\over k+2}q\;.$$ Using \resindBiv once again, we can improve their upper bound. \Theorem [indBvi] Let $k\geq 2$. Then $$r_k(q)\leq \({k^{k+2}\over {(k+1)\log q }}\)^{1/k} q^{k+1\over k}\;.$$ \endproclaimsquare \bigskip\final A {\hifont vertex cover} of a graph $G$ is a set of vertices $U$ so that for every edge $ab\in E(G)$ $a$ or $b$ is a member of $U$. We shall write $\lambda(G)$ for the minimum size of a vertex cover of $G$. The {\hifont vertex cover problem} then is to find a vertex cover $U$ of $G$ in polynomial time, so that $\sizeof{U}/\lambda(G)$ is as small as possible. The main result of Monien and Spekenmeyer's paper \refMoS is to produce an algorithm to find a vertex cover so that this ratio is always at most $2-{\log\log n}/{\log n}$. The bound on the effectiveness of the algorithm depends entirely on the bound which they generate for $r_q(k)$. It is thus unfortunate that although our bound improves on their bound it does so only when $q$ is too large to improve the bound on the algorithms effectiveness. However it should be noted that in generating the bound for \resindBvi for one of the bounds we assumed only that the graph was triangle free. Clearly if some result similar to those contained in this chapter could give a better bound on the independence number of a graph with large odd girth and small average degree an improvement on the bound for $r_q(k)$ and perhaps the effectiveness of Monien and Speckenmeyer's algorithm would be immediate. This improvement could also be passed on to various other polynomial--time algorithms which use the vertex cover algorithm including, for instance, the algorithm of Blum (see \refBl and \refBli~) to colour a 3--chromatic graph in polynomial--time in at most $\hbox{O}(n^{3/8})$ colours. We hope in the future to extend our results to the small degree case. \acknowledge I should like to thank Dr.\thinspace B\'ela Bollob\'as for his helpful advice in the preparation of this paper. \vskip-.5truein\shipoutreferences % \paper [AKSI] {\Aj,\Kom \thinspace and \Sz} {A note on Ramsey Numbers} \JCTA {29} {354--360} 1980 \paper [AKSII] {\Aj,\Kom \thinspace and \Sz} {A dense infinite Sidon sequence} \EJC {2} {1--11} 1981 \proceedings [Bl] {\Bl} {An $\hbox{O}(n^{.4})$--approximation algorithm for 3--colouring ( and improved approximation algorithms for $k$--colouring} {Proceedings of the 21$^{st}$ Annual ACM Symposium on the Theory of Computing} {Seattle, May 1989, pp 535--542} \proceedings [Bli] {\Bl} {Some tools for approximate 3--colouring} {Proceedings of the 31$^{st}$ Annual Symposium on the Foundations of Computer Science} {pp 554--562} \paper [Gri] \Gri {An upper bound on the Ramsey number R(3,k)} \JCTB {35} {145--153} 1983 \paper [MoS] {\Mo \thinspace and \Spe} {Ramsey numbers and an approximation algorithm for the vertex cover problem} \AI {22} {115--123} 1985 \paper [ShI] {\Sh} {A note on the independence number of triangle--free graphs} \DM {46} {83--87} 1983 \paper [ShII] {\Sh} {A note on the independence number of triangle--free graphs, II} \JCTB {53} {300--307} 1991 \endreferences % \bye\end