\magnification=\magstep1
\input amstex
%%
%%
\catcode`\@=11
\ifx\amspptloaded@AmS\relax\catcode`\@=\active
 \endinput\else\let\amspptloaded@AmS\relax\fi
\parindent10\p@
\hsize16.5truecm% it is much better to replace it by, say, 32pc
\vsize23truecm
\normallineskiplimit\p@
\captionwidth@\hsize
\advance\captionwidth@-1.5in
\font@\ninerm=cmr9
\font@\eightrm=cmr8
\font@\sixrm=cmr6
\font@\ninei=cmmi9    \skewchar\ninei='177
\font@\eighti=cmmi8   \skewchar\eighti='177
\font@\sixi=cmmi6     \skewchar\sixi='177
\font@\ninesy=cmsy9   \skewchar\ninesy='60
\font@\eightsy=cmsy8  \skewchar\eightsy='60
\font@\sixsy=cmsy6    \skewchar\sixsy='60
\font@\ninebf=cmbx9
\font@\eightbf=cmbx8
\font@\sixbf=cmbx6
\font@\nineit=cmti9
\font@\eightit=cmti8
\font@\ninesl=cmsl9
\font@\eightsl=cmsl8
%\font@\nineeux=euxm9
%\font@\eighteux=euxm8
%\font@\sixeux=euxm6
%\font@\nineeuy=euym9
%\font@\eighteuy=euym8
%\font@\sixeuy=euym6
\font@\tensmc=cmcsc10
\def\tenpoint{\def\pointsize@{10}%
 \normalbaselineskip12\p@
 \abovedisplayskip12\p@ plus3\p@ minus9\p@
 \belowdisplayskip12\p@ plus3\p@ minus9\p@
 \abovedisplayshortskip\z@ plus3\p@
 \belowdisplayshortskip7\p@ plus3\p@ minus4\p@
 \textonlyfont@\rm\tenrm
 \textonlyfont@\it\tenit
 \textonlyfont@\sl\tensl
 \textonlyfont@\bf\tenbf
 \textonlyfont@\smc\tensmc
 \ifsyntax@\def\big##1{{\hbox{$\left##1\right.$}}}\else
 \let\big\tenbig@
 \textfont\z@\tenrm  \scriptfont\z@\sevenrm  \scriptscriptfont\z@\fiverm
 \textfont\@ne\teni  \scriptfont\@ne\seveni  \scriptscriptfont\@ne\fivei
 \textfont\tw@\tensy \scriptfont\tw@\sevensy \scriptscriptfont\tw@\fivesy
 \textfont\thr@@\tenex \scriptfont\thr@@\tenex \scriptscriptfont\thr@@\tenex
 \textfont\itfam\tenit
 \textfont\slfam\tensl
 \textfont\bffam\tenbf \scriptfont\bffam\sevenbf
  \scriptscriptfont\bffam\fivebf
 %\textfont\euxfam=\teneux
 %\scriptfont\euxfam=\seveneux
 %\scriptscriptfont\euxfam=\fiveeux
 %\textfont\euyfam=\teneuy
 %\scriptfont\euyfam=\seveneuy
 %\scriptscriptfont\euyfam=\fiveeuy
 \fi
 \setbox\strutbox\hbox{\vrule height8.5\p@ depth3.5\p@ width\z@}%
 \setbox\strutbox@\hbox{\vrule height8\p@ depth3\p@ width\z@}%
 \normalbaselines\tenrm\ex@=.2326ex}
\def\eightpoint{\def\pointsize@{8}%
 \normalbaselineskip10\p@
 \abovedisplayskip10\p@ plus2.4\p@ minus7.2\p@
 \belowdisplayskip10\p@ plus2.4\p@ minus7.2\p@
 \abovedisplayshortskip\z@ plus2.4\p@
 \belowdisplayshortskip5.6\p@ plus2.4\p@ minus3.2\p@
 \textonlyfont@\rm\eightrm
 \textonlyfont@\it\eightit
 \textonlyfont@\sl\eightsl
 \textonlyfont@\bf\eightbf
 \ifsyntax@\def\big##1{{\hbox{$\left##1\right.$}}}\else
 \let\big\eightbig@
 \textfont\z@\eightrm \scriptfont\z@\sixrm  \scriptscriptfont\z@\fiverm
 \textfont\@ne\eighti \scriptfont\@ne\sixi  \scriptscriptfont\@ne\fivei
 \textfont\tw@\eightsy \scriptfont\tw@\sixsy \scriptscriptfont\tw@\fivesy
 \textfont\thr@@\tenex \scriptfont\thr@@\tenex \scriptscriptfont\thr@@\tenex
 \textfont\itfam\eightit
 \textfont\slfam\eightsl
 \textfont\bffam\eightbf \scriptfont\bffam\sixbf
   \scriptscriptfont\bffam\fivebf
 %\textfont\euxfam=\eighteux
 %\scriptfont\euxfam=\sixeux
 %\scriptscriptfont\euxfam=\fiveeux
 %\textfont\euyfam=\eighteuy
 %\scriptfont\euyfam=\sixeuy
 %\scriptscriptfont\euyfam=\fiveeuy
 \fi
 \setbox\strutbox\hbox{\vrule height7\p@ depth3\p@ width\z@}%
 \setbox\strutbox@\hbox{\vrule height6.5\p@ depth2.5\p@ width\z@}%
 \normalbaselines\eightrm\ex@=.2326ex}
\def\tenbig@#1{{\hbox{$\left#1\vbox to8.5\p@{}\right.\n@space$}}}
\def\eightbig@#1{{\hbox{$\textfont\z@\ninerm\textfont\tw@\ninesy
 \left#1\vbox to6.5\p@{}\right.\n@space$}}}
\def\footmarkform@#1{$^{#1}$}
\let\thefootnotemark\footmarkform@
\def\makefootnote@#1#2{\insert\footins
 {\interlinepenalty\interfootnotelinepenalty
 \eightpoint\splittopskip\ht\strutbox\splitmaxdepth\dp\strutbox
 \floatingpenalty\@MM\leftskip\z@\rightskip\z@\spaceskip\z@\xspaceskip\z@
 \noindent{#1}\footstrut\ignorespaces#2\unskip\lower\dp\strutbox
 \vbox to\dp\strutbox{}}}
\newcount\footmarkcount@
\footmarkcount@\z@
\def\footnotemark{\let\@sf\empty\relaxnext@\ifhmode\edef
 \@sf{\spacefactor\the\spacefactor}\/\fi
 \def\next@{\ifx[\next\let\next\nextii@\else
  \ifx"\next\let\next\nextiii@\else
  \let\next\nextiv@\fi\fi\next}%
 \def\nextii@[##1]{\footmarkform@{##1}\@sf}%
 \def\nextiii@"##1"{{##1}\@sf}%
 \def\nextiv@{\global\advance\footmarkcount@\@ne
  \footmarkform@{\number\footmarkcount@}\@sf}%
 \futurelet\next\next@}
\def\footnotetext{\relaxnext@
 \def\next@{\ifx[\next\let\next\nextii@\else
  \ifx"\next\let\next\nextiii@\else
  \let\next\nextiv@\fi\fi\next}%
 \def\nextii@[##1]##2{\makefootnote@{\footmarkform@{##1}}{##2}}%
 \def\nextiii@"##1"##2{\makefootnote@{##1}{##2}}%
 \def\nextiv@##1{\makefootnote@{\footmarkform@{\number\footmarkcount@}}{##1}}%
 \futurelet\next\next@}
\def\footnote{\let\@sf\empty\relaxnext@\ifhmode\edef
 \@sf{\spacefactor\the\spacefactor}\/\fi
 \def\next@{\ifx[\next\let\next\nextii@\else
  \ifx"\next\let\next\nextiii@\else
  \let\next\nextiv@\fi\fi\next}%
 \def\nextii@[##1]##2{\footnotemark[##1]\footnotetext[##1]{##2}}%
 \def\nextiii@"##1"##2{\footnotemark"##1"\footnotetext"##1"{##2}}%
 \def\nextiv@##1{\footnotemark\footnotetext{##1}}%
 \futurelet\next\next@}
\def\adjustfootnotemark#1{\advance\footmarkcount@#1\relax}
\let\topmatter\relax
\newbox\titlebox@
\setbox\titlebox@\vbox{}
\Invalid@\overlong
\def\overlong@{\def\next@{\ifx\next\overlong\def\filhss@
 {plus\@m\p@ minus\@m\p@}\def\next@\overlong{\nextii@}\else
 \def\filhss@{plus\@m\p@\relax}\let\next@\nextii@\fi\next@}}
\def\title{\relaxnext@
 \def\nextii@##1\endtitle{{\let\\=\cr
 \global\setbox\titlebox@\vbox{\tabskip\z@\filhss@
 \halign to\hsize{\tenpoint\bf\hfil\ignorespaces####\unskip\hfil\cr##1\cr}}}}%
 \overlong@
 \futurelet\next\next@}
\newif\ifauthor@
\newbox\authorbox@
\def\author{\relaxnext@
 \def\nextii@##1\endauthor{{\let\\=\cr
 \global\setbox\authorbox@\vbox{\tabskip\z@\filhss@
 \halign to\hsize{\tenpoint\smc\hfil\ignorespaces####\unskip\hfil\cr##1\cr
 }}}}\overlong@\global\author@true
 \futurelet\next\next@}
\newif\ifaffil@
\newbox\affilbox@
\def\affil{\relaxnext@
 \def\nextii@{\bgroup\let\\=\cr
 \global\setbox\affilbox@\vbox\bgroup\tabskip\z@\filhss@
 \halign to\hsize\bgroup\tenpoint\hfil\ignorespaces####\unskip\hfil\cr}%
 \overlong@
 \global\affil@true
 \futurelet\next\next@}
\def\endaffil{\cr\egroup\egroup\egroup}
\newcount\addresscount@
\addresscount@\@ne
\def\address#1{\expandafter\gdef\csname address\number\addresscount@
 \endcsname{\noindent\eightpoint\ignorespaces#1\par}\global
 \advance\addresscount@\@ne}
\newif\ifdate@
\def\date#1{\global\date@true\gdef\date@{\tenpoint\ignorespaces#1\unskip}}
\newif\ifthanks@
\def\thanks#1{\global\thanks@true\gdef\thanks@{\eightpoint\ignorespaces
 #1\unskip}}
\Invalid@\nofrills
\Invalid@\usualspace
\newif\ifnofrills@
\def\usualspace@#1{\ifnofrills@\def\usualspace{#1}\fi}
\def\nofrills@#1#2{\def\next@{\ifx\next\nofrills\nofrills@true\let#2\relax
 \def\next@\nofrills{\nextii@}\else\nofrills@false
 \def#2{#1}\let\next@\nextii@\fi\next@}}
\def\thekeywords@{}
\def\keywords{\relaxnext@\nofrills@{{\it Key words and phrases:\enspace}}\keywords@
 \def\nextii@##1{\def\thekeywords@{\usualspace@{{\it\enspace}}\noindent
  \eightpoint\keywords@\ignorespaces##1\par}}%
 \futurelet\next\next@}
\def\thesubjclass@{}
\def\subjclass{\relaxnext@\nofrills@{{\rm 1991 {\it Mathematics Subject
 Classifications}\/\rm: }}\subjclass@
 \def\nextii@##1{\def\thesubjclass@{\usualspace@
  {{\rm\spacefactor2000 \space}}\noindent\eightpoint
  \subjclass@\ignorespaces##1\par}}%
 \futurelet\next\next@}
\def\proclaim{\innerproclaim@}
\def\endproclaim{\innerendproclaim@}
\newif\ifabstract@
\def\theabstract@{}
\def\abstract{\relaxnext@\nofrills@{{\bf Abstract.\enspace}}\abstract@
 \long\def\nextii@##1{\long\gdef\theabstract@{\usualspace@
  {{\eightpoint\enspace}}\eightpoint\abstract@\ignorespaces##1\par}}%
 \global\abstract@true
 \futurelet\next\next@}
\def\pretitle{}
\def\preauthor{}
\def\preaffil{}
\def\predate{}
\def\preabstract{}
\def\prepaper{}
\def\endtopmatter{\hrule height\z@\vskip-\topskip
 \pretitle
 \vskip24\p@ plus12\p@ minus12\p@
 \unvbox\titlebox@
 \preauthor
 \ifauthor@\vskip12\p@ plus6\p@ minus3\p@\unvbox\authorbox@\fi
 \preaffil
 \ifaffil@\vskip10\p@ plus5\p@ minus2\p@\unvbox\affilbox@\fi
 \predate
 \ifdate@\vskip6\p@ plus2\p@ minus\p@\hbox to\hsize{\hfil\date@\hfil}\fi
 \preabstract
 \ifthanks@\makefootnote@{}{\thanks@}\fi
 \ifabstract@\vskip15\p@ plus12\p@ minus12\p@
  {\leftskip24\p@\rightskip24\p@\noindent\theabstract@}\fi
 \prepaper
 \outer\def\proclaim{\innerproclaim@}%
 \outer\def\endproclaim{\innerendproclaim@}%
 \vskip18\p@ plus12\p@ minus6\p@\tenpoint}
\newcount\addressnum@
\outer\def\enddocument{\nobreak\sfcode`\.=3000 \vskip12\p@ minus6\p@
 \thekeywords@\thesubjclass@\nobreak\vskip12\p@ minus6\p@\addressnum@\z@
 \loop\ifnum\addressnum@<\addresscount@\advance\addressnum@\@ne
 \csname address\number\addressnum@\endcsname\repeat
 \vfill\supereject\end}
\newbox\headingbox@
\outer\def\heading{\relaxnext@
 \def\nextii@{\bigbreak\bgroup\let\\=\cr
 \global\setbox\headingbox@\vbox\bgroup\tabskip\z@\filhss@
 \halign to\hsize\bgroup\tenpoint\smc\hfil\ignorespaces####\unskip\hfil\cr}%
 \overlong@
 \futurelet\next\next@}
\def\endheading{\cr\egroup\egroup\egroup\unvbox\headingbox@
 \nobreak\medskip}
\def\subheading{\relaxnext@\nofrills@{.\enspace}\subheading@
 \def\nextii@##1{\medbreak%\noindent
{\usualspace@{{\bf\enspace}}%
  \tenpoint\bf\ignorespaces##1\unskip\subheading@}\ignorespaces}%
 \futurelet\next\next@}
\newif\ifproclaim@
\def\innerproclaim@{\relaxnext@\nofrills@{.\enspace}\proclaim@
 \def\nextii@##1{\medbreak\noindent\def\next{8}%
  \ifx\pointsize@\next\uppercase
  {\usualspace@{{\rm\enspace}}\ignorespaces\rm##1\unskip\proclaim@}\else
  {\usualspace@{{\smc\enspace}}\smc\ignorespaces##1\unskip\proclaim@}\fi\sl
  \ifproclaim@\Err@{Previous \expandafter
 \eat@\string\\proclaim has no matching \expandafter
 \eat@\string\\endproclaim}\else\proclaim@true\fi\ignorespaces}%
 \futurelet\next\next@}
\def\innerendproclaim@{\proclaim@false\par\rm
 \ifdim\lastskip<\medskipamount\removelastskip\penalty55 \medskip\fi}
\def\demo{\relaxnext@\nofrills@{.\enspace}\demo@
 \def\nextii@##1{\par\ifdim\lastskip<\smallskipamount\removelastskip
  \smallskip\fi%\noindent
{\usualspace@{{\sl\enspace}}%
  \sl\ignorespaces##1\unskip\demo@}\rm
  \ifproclaim@\Err@{Previous \expandafter
  \eat@\string\\proclaim had no matching \expandafter
  \eat@\string\\endproclaim}\fi\ignorespaces}%
 \futurelet\next\next@}
\def\enddemo{\par\smallskip}
\def\qed{\ifhmode\unskip\nobreak\fi\ifmmode\ifinner\else\hskip5\p@\fi\fi
 \hbox{\hskip5\p@\lower 1.5 pt\hbox{\vrule width .2 pt 
\vbox{\hrule width 4 pt height .2 pt \vskip 7.1 pt\hrule width 4 pt 
height .2 pt }\unskip\vrule width .2 pt}\hskip\p@}}
\def\cite#1{\relaxnext@
 \def\nextiii@##1,##2\end@{[{\bf##1},##2]}%
 \in@,{#1}\ifin@\def\next{\nextiii@#1\end@}\else
 \def\next{[{\bf#1}]}\fi\next}
\newcount\rostercount@
\newif\iffirstitem@
\newtoks\everypartoks@
\let\plainitem@\item
\def\par@{\everypartoks@=\expandafter{\the\everypar}\everypar{}}
\def\roster{\edef\leftskip@{\leftskip\the\leftskip}\relaxnext@
 \rostercount@\z@\def\item{\futurelet\next\rosteritem@}%
 \def\next@{\ifx\next\runinitem\let\next\nextii@\else
  \let\next\nextiii@\fi\next}%
 \def\nextii@\runinitem{\unskip
  \def\next@{\ifx\next[\let\next\nextii@\else
   \ifx\next"\let\next\nextiii@\else\let\next\nextiv@\fi\fi\next}%
  \def\nextii@[####1]{\rostercount@####1\relax
   \enspace{\rm(\number\rostercount@)}~\ignorespaces}%
  \def\nextiii@"####1"{\enspace{\rm####1}~\ignorespaces}%
  \def\nextiv@{\enspace{\rm(1)}\rostercount@\@ne~}%
  \par@\firstitem@false
  \futurelet\next\next@}%
 \def\nextiii@{\par\par@\penalty\@m\smallskip\vskip-\parskip
  \firstitem@true}%
 \futurelet\next\next@}
\def\rosteritem@{\iffirstitem@\firstitem@false\else\par\vskip-\parskip\fi
 \leftskip3\parindent\noindent
 \def\next@[##1]{\rostercount@##1\relax
  \llap{\hbox to2.5\parindent{\hss\rm(\number\rostercount@)}\hskip
  .5\parindent}\ignorespaces}%
 \def\nextii@"##1"{%
  \llap{\hbox to2.5\parindent{\hss\rm##1}\hskip.5\parindent}\ignorespaces}%
 \def\nextiii@{\advance\rostercount@\@ne
  \llap{\hbox to2.5\parindent{\hss\rm(\number\rostercount@)}\hskip
  .5\parindent}}%
 \ifx\next[\let\next\next@\else\ifx\next"\let\next\nextii@\else
 \let\next\nextiii@\fi\fi\next}
\def\therosteritem#1{{\rm(\ignorespaces#1\unskip)}}
\newif\ifnextRunin@
\def\endroster{\relaxnext@\par\leftskip@
 \penalty-50 \vskip-\parskip\smallskip
 \def\next@{\ifx\next\Runinitem\let\next@\relax
  \else\nextRunin@false\let\item\plainitem@\ifx\next\par
  \def\next@\par{\everypar=\expandafter{\the\everypartoks@}}%
  \else\def\next@{\noindent\everypar=\expandafter{\the\everypartoks@}}%
  \fi\fi\next@}%
 \futurelet\next\next@}
\newcount\rosterhangafter@
\def\Runinitem#1\roster\runinitem{\relaxnext@\rostercount@\z@
 \def\item{\futurelet\next\rosteritem@}%
 \def\runinitem@{#1}%
 \def\next@{\ifx\next[\let\next\nextii@\else\ifx\next"\let\next\nextiii@
  \else\let\next\nextiv@\fi\fi\next}%
 \def\nextii@[##1]{\rostercount@##1\relax\def\item@{{\rm(\number
  \rostercount@)}}\nextv@}%
 \def\nextiii@"##1"{\def\item@{{\rm##1}}\nextv@}%
 \def\nextiv@{\advance\rostercount@\@ne\def\item@{{\rm(\number
  \rostercount@)}}\nextv@}%
 \def\nextv@{\setbox\z@\vbox
  {\ifnextRunin@\noindent\fi
  \runinitem@\unskip\enspace\item@~\par
  \global\rosterhangafter@\prevgraf}%
  \firstitem@false\ifnextRunin@\else\par\fi
  \hangafter\rosterhangafter@\hangindent3\parindent
  \ifnextRunin@\noindent\fi\runinitem@\unskip\enspace
  \item@~\ifnextRunin@\else\par@\fi\nextRunin@true\ignorespaces}%
 \futurelet\next\next@}
\outer\def\Refs{\relaxnext@\def\refskip@{\hskip\@ne sp\hskip\m@ne sp}%
 \def\next@{\ifx\next\nofrills\def\next@\nofrills{\nextii@}\else
  \def\next@{\nextii@{References}}\fi\next@}%
 \def\nextii@##1{\bigbreak\hbox to\hsize{\hfil\tenpoint
  \smc\ignorespaces##1\unskip\hfil}\nobreak
  \bigskip\eightpoint\sfcode`.=\@m}%
 \futurelet\next\next@}
\newbox\nobox@        \newbox\keybox@        \newbox\bybox@
\newbox\bysamebox@    \newbox\paperbox@      \newbox\paperinfobox@
\newbox\jourbox@      \newbox\volbox@        \newbox\issuebox@
\newbox\yrbox@                               \newbox\pagesbox@
\newbox\bookbox@
\newbox\bookinfobox@  \newbox\publbox@       \newbox\publaddrbox@
\newbox\finalinfobox@
\newif\ifno@          \newif\ifkey@          \newif\ifby@ \newif\ifmanyby@
\newif\ifbysame@      \newif\ifpaper@        \newif\ifpaperinfo@
\newif\ifjour@        \newif\ifvol@          \newif\ifissue@
\newif\ifyr@ \newif\iftoappear@              \newif\ifpages@ \newif\ifpage@
\newif\ifbook@ \newif\ifinbook@
\newif\ifbookinfo@    \newif\ifpubl@         \newif\ifpubladdr@
\newif\iffinalinfo@   \newif\ifafterbook@
\newif\iffirstref@    \newif\iflastref@      \newif\ifprevjour@
\newif\ifprevbook@    \newif\ifprevinbook@   \newif\ifnojourinfo@
\newdimen\maxbysamerule@
\maxbysamerule@1in
\def\ref@{\global\no@false\global\key@false\global\by@false
 \global\bysame@false\global\paper@false\global\paperinfo@false
 \global\jour@false\global\vol@false\global\issue@false
 \global\yr@false\global\toappear@false\global\pages@false\global\page@false
 \global\book@false\global\inbook@false
 \global\bookinfo@false\global\publ@false\global\publaddr@false
 \global\finalinfo@false
 \bgroup\ignorespaces}
\Invalid@\moreref
\outer\def\ref{\begingroup
 \noindent\hangindent20\p@\hangafter\@ne\firstref@true
 \lastref@false\def\moreref{\egroup\endref@\global\firstref@false\ref@}\ref@}
\def\refdef@#1#2{\def#1{\egroup
 \csname\expandafter\eat@\string#1@true\endcsname
 \expandafter\setbox
 \csname\expandafter\eat@\string#1box@\endcsname\hbox\bgroup#2}}
\refdef@\no\relax \refdef@\key\relax
\def\manyby{\egroup\global\manyby@true\by@true\setbox\bybox@\hbox\bgroup}
\def\by{\egroup\by@true\bysame@false\global\manyby@false
 \setbox\bybox@\hbox\bgroup}
\def\bysame{\egroup\bysame@true\bgroup}
\refdef@\paper\it
\refdef@\paperinfo\relax
\def\jour{\egroup\jour@true\prevjour@true\setbox
 \jourbox@\hbox\bgroup}
\refdef@\vol\bf
\refdef@\issue\relax \refdef@\yr\relax
\def\toappear{\egroup\toappear@true\bgroup}
\refdef@\pages\relax
\def\page{\egroup\page@true\setbox\pagesbox@\hbox\bgroup}
\refdef@\book\relax
\def\inbook{\egroup\inbook@true\previnbook@true\setbox
 \bookbox@\hbox\bgroup}
\refdef@\bookinfo\relax
\refdef@\publ\relax
\refdef@\publaddr\relax
\refdef@\finalinfo\relax
\def\setpunct@{\def\prepunct@{\ifnum\lastpenalty<0
 \edef\penalty@{\penalty\the\lastpenalty}\unpenalty,\ifafterbook@''\fi
  \penalty@\relax\space\else
 \ifdim\lastskip=\@ne sp\unskip\unskip
 \edef\penalty@{\penalty\the\lastpenalty}\unpenalty,\ifafterbook@''\fi
  \penalty@\relax\space
 \else,\ifafterbook@''\fi\space\fi\fi\afterbook@false}}
\def\ppunbox@#1{\prepunct@\unhbox#1\unskip}
\def\endref@{\let\prepunct@\relax
 \iffirstref@
  \ifno@\hbox to20\p@{\hss\unhbox\nobox@\unskip. }\else\hbox to10\p@{}\fi
  \ifkey@\unhbox\keybox@\unskip\ \fi
  \ifmanyby@
   \ifby@\hbox{\unhcopy\bybox@\unskip}\setpunct@
  \global\setbox\bysamebox@\hbox{\unhcopy\bybox@\unskip}\else
  \ifbysame@\ifdim\wd\bysamebox@>\maxbysamerule@
    \hbox to\maxbysamerule@{\leaders\hrule\hfill}\else
    \hbox to \wd\bysamebox@{\leaders\hrule\hfill}\fi\setpunct@\fi
   \fi
  \else
  \ifby@\unhcopy\bybox@\unskip\setpunct@\fi\fi
 \fi
 \ifpaper@\ppunbox@\paperbox@\setpunct@\fi
 \ifpaperinfo@\ppunbox@\paperinfobox@\setpunct@\fi
 \ifjour@\ppunbox@\jourbox@\setpunct@
   \ifvol@\ \unhbox\volbox@\unskip\setpunct@\fi
   \ifissue@\ \unhbox\issuebox@\unskip\setpunct@\fi
   \ifyr@\ (\unhbox\yrbox@\unskip)\setpunct@\fi
   \iftoappear@\ (to appear)\setpunct@\fi
   \ifpages@\ppunbox@\pagesbox@\setpunct@\fi
   \ifpage@\prepunct@ p.\ \unhbox\pagesbox@\unskip\setpunct@\fi
 \else
  \ifprevjour@\unskip\nojourinfo@false
   \ifvol@\else\ifissue@\else\ifyr@\else\nojourinfo@true\fi\fi\fi
   \ifnojourinfo@\else,\fi
   \ifvol@\ \unhbox\volbox@\unskip\setpunct@\fi
   \ifissue@\ \unhbox\issuebox@\unskip\setpunct@\fi
   \ifyr@\ (\unhbox\yrbox@\unskip)\setpunct@\fi
   \iftoappear@\ (to appear)\setpunct@\fi
   \ifpages@\ppunbox@\pagesbox@\setpunct@\fi
   \ifpage@\prepunct@ p.\ \unhbox\pagesbox@\unskip\setpunct@\fi
  \fi
 \fi
 \ifbook@\prepunct@``\unhbox\bookbox@\unskip\afterbook@true\setpunct@\fi
 \ifinbook@\prepunct@\unskip\ in ``\unhbox\bookbox@\unskip\afterbook@true
  \setpunct@\global\book@true\fi
 \ifbookinfo@\ppunbox@\bookinfobox@\setpunct@\fi
 \ifpubl@\ppunbox@\publbox@\setpunct@\fi
 \ifpubladdr@\ppunbox@\publaddrbox@\setpunct@\fi
 \ifbook@
  \ifyr@\prepunct@\unhbox\yrbox@\unskip\setpunct@\fi
  \iftoappear@\ifafterbook@''\fi\ (to appear)\afterbook@false
   \setpunct@\fi
  \ifpages@\prepunct@ pp.\ \unhbox\pagesbox@\unskip\setpunct@\fi
  \ifpage@\prepunct@ p.\ \unhbox\pagesbox@\unskip\setpunct@\fi
 \else
  \ifprevinbook@\unskip
   \ifyr@\prepunct@\unhbox\yrbox@\unskip\setpunct@\fi
   \iftoappear@\ (to appear)\setpunct@\fi
   \ifpages@\prepunct@ pp.\ \unhbox\pagesbox@\unskip\setpunct@\fi
   \ifpage@\prepunct@ p.\ \unhbox\pagesbox@\unskip\setpunct@\fi
  \fi
 \fi
\iffinalinfo@.\ifafterbook@''\fi\afterbook@false
\spacefactor3000\relax\space\unhbox\finalinfobox@\else
 \iflastref@.\ifafterbook@''\fi\afterbook@false\else;\ifafterbook@''\fi
  \afterbook@false\space\fi
\fi}
\def\endref{\egroup\global\lastref@true\endref@\global\prevjour@false\global
 \previnbook@false\par\endgroup}
\newif\iflogo@
\def\nologo{\logo@false}
\logo@true
\output={\output@}
\def\output@{%
 \ifnum\pageno=\@ne\shipout\vbox{\vbox to\vsize
  {\boxmaxdepth\maxdepth\pagecontents}\baselineskip2pc
  \iflogo@\hbox to\hsize{\hfil\eightpoint The Electronic Journal of Combinatorics 1 (1994), \#R4}\fi}\else
 \shipout\vbox{\vbox to\vsize
  {\boxmaxdepth\maxdepth\pagecontents}\baselineskip2pc
  \hbox to\hsize{\hfil\tenpoint\number\pageno\hfil}}%
 \fi
 \global\advance\pageno\@ne
 \ifnum\outputpenalty>-\@MM\else\dosupereject\fi}
\def\footnoterule{\vskip-3\p@\hrule width 2truein \vskip 2.6\p@}
\tenpoint
\catcode`\@=\active
\def\styname{amsppt}\def\styversion{1.0}
%%%
%%%
%\baselineskip=16pt
\NoBlackBoxes
\redefine\E{\operatorname{E}}
\redefine\P{\operatorname{Prob}}
\redefine\Var{\operatorname{Var}}
%%
\redefine\db#1#2{\dsize\binom{#1}{#2}}
\redefine\df#1#2{\dsize\frac{#1}{#2}}
\define\){\right)}                    
\define\]{\right]}
\define\({\left(}
\define\[{\left[}
\define\lb{\left\{}
\define\rb{\right\}}
\define\ov{\overrightarrow}
%\redefine\i{\infty}
\redefine\d{\delta}
\redefine\ep{\epsilon}
\redefine\i{\infty}
\redefine\o{\omega}
%%
\topmatter
\title
ON RAMSEY MINIMAL GRAPHS
\endtitle
\author
Tomasz \L uczak\footnote"{}"{Department of Mathematics 
and Computer Science, 
Emory University, Atlanta, Georgia 30322.
On leave from Mathematical Institute of the Polish Academy of Sciences, 
 and Adam Mickiewicz University, Pozna\'n, Poland. Research
partially supported by~KBN grant~2~1087~91~01.}
\endauthor
\abstract{An elementary probabilistic argument is presented 
which shows  that for every forest~$F$ other than  a matching,
and  every graph $G$ containing a  cycle, there exists
an infinite number of graphs $J$ such that $J\to (F,G)$ but 
if we delete from $J$  any edge~$e$ the graph $J-e$ obtained in this 
way does not have this property. }
\keywords{critical graphs, Ramsey theory}
\subjclass{05D10, 05C80}
\endtopmatter

\document

\subheading{Introduction} All graphs in this note
are undirected graphs, without loops and multiple edges, 
containing no isolated points. We use the arrow notation of
Rado, writing $J\to (G,H)$ whenever each colouring of 
edges of $J$ with two colours, say, black and white, 
 leads to either black copy of $G$ or white copy of $H$. 
We say that $J$ is {\sl critical} for a pair $(G,H)$
if $J\to(G,H)$ but for every edge $e$ of $J$ we have 
$J-e\not \to (G,H)$.  The pair $(G,H)$ is called 
{\sl Ramsey-infinite} or {\sl Ramsey-finite} according to whether 
the class of all graphs critical for $(G,H)$ is a finite or 
infinite set. 

The problem of characterizing Ramsey-infinite pairs of graphs
has been addressed in numerous papers (see [1--7, 9] and [8] for a brief 
survey of most important facts). In particular, 
basically all Ramsey-finite pairs consisting  of two forests 
are specified in a theorem of Faudree  [7] and a  recent
result of R\"odl and Ruci\'nski [10, Corollary 2] 
implies that if $G$ contains a cycle then the pair $(G,G)$
is Ramsey-infinite.   The main result of this note states
that each pair which consists of a non-trivial forest and 
a non-forest is Ramsey-infinite. 

\proclaim{Theorem 1} If $F$ is a forest other than a matching
and $G$ is a graph containing at least one cycle then the pair
$(F,G)$ is Ramsey-infinite.
\endproclaim

Since, as we have already  mentioned, minimal Ramsey properties 
for pairs consisting of two forests
have been well studied,   Theorem ~1 has   
  two immediate consequences.

\proclaim{Corollary 2} Let $F$ be a forest which does not
consist solely of stars. Then $(F,G)$ is Ramsey-finite if and only if $G$ 
is a matching.\qed
\endproclaim

\proclaim{Corollary 3} Let $K_{1,2m}$ denote a star with $2m$ rays. 
 Then $(K_{1,2m},G)$ is Ramsey-finite if and only if $G$ is a matching.\qed
\endproclaim


\subheading{Proof of Theorem 1} We shall deduce Theorem~1 from the following
lemma, a probabilistic  proof of which we postpone until the next section. 
Here and below, we denote by  $V(G)$ and $E(G)$ sets of vertices and edges of 
 a graph $G$, respectively, and set  $v(G)=|V(G)| $ and $e(G)=|E(G)|$.
  
\proclaim{Lemma 4} Let $G$ be a graph with at least one cycle and $m, r$
be natural numbers. Then there exists a subgraph $H$  of $G$ containing 
a cycle, and a graph $J=J(m,r,G)$  on $n$ vertices,  such that: 
\roster
\item"(a)" $J$ contains at least $3mn$ edge-disjoint copies of
$G$,
\item"(b)" every subgraph of $J$ with $s$ vertices, where $s\le r$, 
contains at most \newline
$(s-1)e(H)/(v(H)-1)$ edges. 
\endroster
\endproclaim

\demo{Proof of Theorem 1} Let $F$ be any forest on $m$ vertices, other
than a matching, and let~$G$ be a graph containing at least one cycle. 
We shall show that for every $r$ there
exists a graph with more than $r$ vertices which is critical 
for $(F,G)$. Thus, let $J=J(m,r,G)$ be the graph whose existence is 
guaranteed by Lemma~4, and $\tilde J$ be a graph
spanned in $J$ by some $3mn$ edge-disjoint copies of $G$.
  Colour edges of $\tilde J$  black and white. 
If there are at least  $2mn$ edges coloured black,  then 
 $\tilde J$ contains a black copy of $F$, since Tur\'an's number for the forest
on $m$ vertices is  smaller than $2mv(\tilde J)\le 2mn$. On the other 
hand, if the colouring contains  less than $2mn$ black edges, 
they miss at least $mn$ copies of $G$, i.e. at least one copy 
of $G$ is coloured white. Thus,  $\tilde J\to (F,G)$. 

Furthermore,  for any subgraph $K$ of $\tilde J$ on  $s$
vertices, $s\le r$, we have $K\not\to (F,G)$. More
specifically, we shall show that there is a black and white colouring of
edges of $K$ such that black edges form a matching and every 
{\sl proper} copy  of $H$, i.e. a copy which is 
 contained in some copy of $G$, has at least one edge coloured black.
Indeed, observe first that the upper bound for the density
of subgraphs of $J$ implies that each copy of $H$ in $G$ is induced
and each  two proper copies  have at most  one vertex in common 
(note that since all copies of~$G$ are edge-disjoint, proper copies
of $H$  can not share an edge).
Thus, let $H_1\subseteq K$ be  a proper copy of $H$.
Then, either no other proper copy of $H$ shares with  $H_1$ 
a vertex, and then we may colour one edge of $H_1$ black and 
all other edges of $K$  incident to vertices of~$H_1$ white,
 or~$K$ contains another proper copy of~$H$, say~$H_2$, which has 
with~$H_1$ a vertex in common. But then the upper bound given by (b)
implies that a subgraph spanned in $K$ by $V(H_1) \cup V(H_2)$ 
contains no other edges but those which belong to $E(H_1)\cup E(H_2)$.
In such a way  one can find  a sequence of proper copies of $H$, 
say, $H_1, H_2, \dots, H_t$, such that 
\roster
\item"(i)"
$H_i$ share only one vertex, say $v_i$,  with $\bigcup_{j=1}^{i-1} V(H_j)$,
 for every  $i=2,3,\dots, t$,
\item"(ii)" all edges of the subgraph spanned by $\bigcup_{j=1}^t V(H_j)$ 
are those from   $\bigcup_{j=1}^t E(H_j)$,
\item"(iii)" 
for each proper copy $H'$ of $H$ contained in $K$ we have
$ V(H')\cap\bigcup_{j=1}^t V(H_j)=\emptyset$. 
\endroster
Now, pick as $e_1$ any edge of $H_1$ and  for $i=2,3,\dots,t$,
 choose one edge $e_i$
of  $H_i$ which does not contain vertex $v_i$ (since
$H$ contains a cycle, such an edge always exists). 
Clearly,  edges~$e_i$, $i=1,2,\dots, t$, form a matching.
Colour them black and all other edges adjacent 
to   $\bigcup_{j=1}^{i-1} V(H_j)$ colour white. 
Obviously, in such a way  we  can colour  each `cluster' of proper
copies of $H$ contained in $K$, destroying all white copies of
$G$ and creating no black copies of $F$,  so $K\not\to (F,G)$.

Thus, we have shown that $\tilde J\to (F,G)$ but for every
subgraph~$K$ of~$\tilde J$ with at most~$r$ vertices we have 
$K\not\to(F,G)$. Consequently, any subgraph contained in $\tilde J$
 critical for $(F,G)$ must contain more than $r$ vertices
and the assertion follows.\qed


\subheading{Proof of Lemma~4} Let $G$ be a graph with at least one cycle and
$$m(G)=\max\Big\{\df{e(H)}{v(H)-1}: H\subseteq G, v(H)\ge 2\Big\}\;.$$
Call a subgraph $H$ of $G$ {\sl extremal} if $m(G)=e(H)/(v(H)-1)$.
Note that since $G$ contains a cycle, each extremal 
subgraph of $G$ must contain a cycle as well. 
Furthermore, denote by $G(n,p)$ a standard binomial model of 
a random graph on $n$ vertices, in which each pair of vertices 
appears as an edge independently with probability $p$.

\proclaim {Lemma 5} Let $G$ be a graph,  $r$ be a natural number  and 
$p=p(n)=n^{-1/m(G)}\log n$. Then, with probability tending to~1 as 
$n\to\i$, $G(n,p)$ has the following two properties:
\roster
\item "(a)" $G(n,p)$ contains at least 
$n(\log n)^2$ edge-disjoint copies of $G$,
\item "(b)" $G(n,p)$ contains less than $n/\log n$ subgraphs on $s$ vertices, 
$s\le r$,   with more than $(s-1) m(G)$ edges.
\endroster
\endproclaim

\demo{Proof} Let $\Cal F$ be a random family of copies of $G$ in $G(n,p)$ 
such that  the probability that a given  copy of $G$ in $G(n,p)$ 
belongs to $\Cal F$ is equal to 
$$\rho=4v(G)!\df{n(\log n)^2}{n^{v(G)}p^{e(G)}}\;,$$ 
independently for each copy. Furthermore, denote by $X$ the size of 
$\Cal F$. Then, for the expectation of $X$, we have 
$$ 3n(\log n)^2\le \binom n{v(G)} p^{e(G)}\rho\le\E X\le 
 n^{v(G)} p^{e(G)}\rho= O(n(\log n)^2)\;,$$
where here and below we assume all inequalities to hold only for $n$ large
enough. 
The second factorial moment of $X$ can be decomposed into two
parts: $\E'_2 X$, which counts the expected number of 
pairs of edge-disjoint copies from $\Cal F$, and $\E''_2 X$ 
related to those pairs of copies which share at least one edge. 
$\E'_2 X$ can  be easily shown to be equal to $(\E X)^2 (1+O(1/n))$, 
whereas for the upper bound for $\E''_2 X$ we get
$$\aligned 
\E''_2 X&\le  \sum_{J\subseteq G} n^{v(J)}p^{e(J)}
n^{2(v(G)-v(J))}p^{2(e(G)-e(J))} \rho^2
\le O(n^2 (\log n)^2)\sum_{J\subseteq G} n^{-v(J)}p^{-e(J)}\\ 
&\le O\Big(\df{n}{\log n}\Big)\sum_{J\subseteq G} 
n^{e(J)(1/m(G)-(v(J)-1)/e(J))}=O\Big(\df n{\log n}\Big)\;.
\endaligned\tag{$*$}$$
Thus, 
$$\Var X = \E_2 X+\E X-(\E X)^2= \E_2' X+\E''_2 X+\E X -(\E X)^2
=O(\E X (\log n)^2)\;,$$
and, from Chebyshev's inequality, $X\ge 2\E X/3\ge 2n(\log n)^2$
with probability tending to ~1 as $n\to\infty$. 
Furthermore, note that  ($*$) implies that  the expected number of copies
of $G$ in $\Cal F$ which share an edge with another member of $\Cal F$ 
is $O(n/\log n)$, so, from Markov's inequality, with probability 
at least $1-O(1/\log n)$, the number of such copies in $\Cal F$ 
is smaller than $n$.
Thus, with probability tending to 1 as $n\to\infty$, family
 $\Cal F$ contains at least $n(\log n)^2$ edge-disjoint copies of $G$
and the first part of the assertion follows.

In order to verify (b) let $Y$ denote the number of subgraphs of $G(n,p)$
of size $s$, $s\le r$, with more than  $(s-1)m(G)$ edges, 
and define $\ep>0$ as  
$$\ep=\min\{\lfloor  (s-1) m(G)\rfloor+1-(s-1)m(G)
 : 1\le s\le r \big\}\;.$$
Then 
$$
\E Y\le \sum_{s=1}^r\sum_{t= \lfloor(s-1) m(G)\rfloor+1}^{\binom s2}
n^s 2^{\binom s2} p^t \le O\big(n^{1-\ep/m(G)}(\log n)^{\binom r2}\big)
=O(n/(\log n)^2)\;.$$
Hence, from Markov's inequality, with probability tending to ~1
as $n\to\infty$ the number of such subgraphs is smaller than $n/\log n$.\qed

\demo{Proof of Lemma 4} From Lemma~5 it follows that for every 
graph $G$ which is not a forest, 
and for every  natural number $r$, one can find $N$ such that 
for each $n\ge N$ there exists a graph $\hat J_n$ on $n$ vertices 
such that $\hat J_n$ contains at least $n(\log n)^2$ disjoint copies of~$G$ 
and the number of subgraphs of $\hat J_n$  with $s$ vertices, $s\le r$, 
and more than  $(s-1)m(G)$ edges, is smaller than $n/\log n$. 
Let $n=\max\{N, e^{r^2}, e^{2m}\} $. Then, $\hat J_n$ contains 
at least $4 m^2 n$ edge-disjoint copies of $G$ and not more
than $r^2 n/\log n\le n$ edges which belong to `dense' small subgraphs. 
Thus, removing these edges from $\hat J_n$ results 
in a graph $J(m,r,G)$ without dense small subgraphs  which contains  
at least $4m^2 n-n\ge 3mn$ edge-disjoint copies of ~$G$.\qed
  

\Refs


\ref
\key[1]
\by S.A.Burr, P.Erd\H os, R.J.Faudree, C.C.Rousseau
 and R.H.Schelp
\paper An extremal problem in generalized Ramsey theory
\jour Ars Combin.
\vol 10
\yr 1980
\pages 193--203
\endref

\ref
\key[2]
\by S.A.Burr, P.Erd\H os, R.J.Faudree, C.C.Rousseau
 and R.H.Schelp
\paper Ramsey minimal graphs for the pair star-connected graph
\jour Studia Scient.Math.Hungar.
\vol 15
\yr 1980
\pages 265--273
\endref

\ref
\key[3]
\by S.A.Burr, P.Erd\H os, R.J.Faudree, C.C.Rousseau
 and R.H.Schelp
\paper Ramsey minimal graphs for star forests
\jour Discrete Math. 
\vol 33
\yr 1981
\pages 227--237
\endref

\ref
\key[4]
\by S.A.Burr, P.Erd\H os, R.J.Faudree, C.C.Rousseau
 and R.H.Schelp
\paper Ramsey minimal graphs for matchings
\paperinfo in {\sl The Theory and Applications of Graphs} (G.Chartrand, ed.)
Wiley (1981) pp.159--168
\endref

\ref
\key[5]
\by S.A.Burr, P.Erd\H os, R.J.Faudree, C.C.Rousseau
 and R.H.Schelp
\paper Ramsey minimal graphs for  forests
\jour Discrete Math. 
\vol 38
\yr 1982
\pages 23--32
\endref


\ref
\key[6]
\by S.A.Burr, P.Erd\H os, R.J.Faudree  and R.H.Schelp
\paper A class of Ramsey-finite  graphs
\paperinfo in {\sl Proc.9th S.E.Conf.\ on Combinatorics, Graph Theory
and Computing} (1978)  pp.171--178
\endref

\ref
\key[7]
\by  R.J.Faudree 
\paper Ramsey minimal graphs for  forests
\jour Ars Combin. 
\vol 31
\yr 1991
\pages 117--124
\endref

\ref
\key[8]
\by   R.J.Faudree, C.C.Rousseau and R.H.Schelp
\paper Problems in graph theory from Memphis
\paperinfo preprint
\endref

\ref
\key[9]
\by  J.Ne\v set\v ril and  V.R\"odl
\paper  The structure of critical graphs
\jour Acta Math.Acad.Sci.Hungar.
\vol 32
\yr 1978
\pages 295--300
\endref

\ref
\key [10]
\by V.R\"odl and A.Ruci\'nski
\paper Threshold functions for Ramsey properties
\paperinfo submitted
\endref


\enddocument