%\magnification=\magstep1
%\nopagenumbers
\font\bigrm=cmr17
\font\medrm=cmr12
\font\medbf=cmbx12
\def\sc{\it}
\def\sectioncount{\count11}
\sectioncount=0
\def\theoremcount{\count12}
\theoremcount=0
\def\lemmacount{\count13}
\lemmacount=0
\def\corollarycount{\count14}
\corollarycount=0
\def\exerciseno{\count15}
\exerciseno=0
\def\algorithmcount{\count16}
\algorithmcount=0
\def\figurecount{\count17}
\figurecount=0
\def\ex{\advance\exerciseno by 1
        \item{\the\exerciseno.}
       }
\def\section#1{\advance\sectioncount by 1
     \medskip
     {\par \noindent \bf\the\sectioncount.\enskip #1.}
     \medskip
%     \headline={{\sl #1\hfil\the\pageno}}
     \theoremcount=0
     \lemmacount=0
     \corollarycount=0
    }
\long\def\longtheorem#1{\advance\theoremcount by 1
      \medskip
      {\bf\noindent Theorem \the\sectioncount.\the\theoremcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\theorem#1{\advance\theoremcount by 1
      \medskip
      {\bf\noindent Theorem \the\sectioncount.\the\theoremcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longlemma#1{\advance\lemmacount by 1
      \medskip
      {\bf\noindent Lemma \the\sectioncount.\the\lemmacount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\lemma#1{\advance\lemmacount by 1
      \medskip
      {\bf\noindent Lemma \the\sectioncount.\the\lemmacount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longcorollary#1{\advance\corollarycount by 1
      \medskip
      {\bf\noindent Corollary \the\sectioncount.\the\corollarycount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\corollary#1{\advance\corollarycount by 1
      \medskip
      {\bf\noindent Corollary \the\sectioncount.\the\corollarycount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longalgorithm#1{\advance\algorithmcount by 1
      \medskip
      {\bf\noindent Algorithm \the\sectioncount.\the\algorithmcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\algorithm#1{\advance\algorithmcount by 1
      \medskip
      {\bf\noindent Algorithm \the\sectioncount.\the\algorithmcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\figure#1#2#3{\advance\figurecount by 1
                \vbox{
                      \vskip #1
                      \special{psfile="#2"}
                      \vskip .3true in
                      \centerline{Figure\ \the\figurecount.}
                     }
                \medskip
                \figurelabel{#3}
            }
\def\proof{{\bf\noindent Proof}:\enskip}
%\def\qed{\hfill \vrule width4pt height8pt depth0pt}
\def\qed{\hfill\vbox to 4pt{\hrule\hbox to 4pt
            {\vrule height 3pt depth 0pt \hfill \vrule}\vfill\hrule}
            \medskip
            }
\def\exerciselabel#1{\edef#1{\the\exerciseno}}
\def\theoremlabel#1{\edef#1{\the\sectioncount.\the\theoremcount}}
\def\lemmalabel#1{\edef#1{\the\sectioncount.\the\lemmacount}}
\def\corollarylabel#1{\edef#1{\the\sectioncount.\the\corollarycount}}
\def\algorithmlabel#1{\edef#1{\the\sectioncount.\the\algorithmcount}}
\def\figurelabel#1{\edef#1{\the\figurecount}}
\def\svs#1{{\sl S}_{#1}}
\def\dsvs#1{\dual{{\sl S}_{#1}}}
\def\dual#1{#1^*}
\def\comp#1{{\overline #1}}
\def\bibitem#1#2{
        \vbox{
          \smallskip\noindent \hangindent2\parindent \textindent{[#1]\ } #2}
        }
\def\Z{{\bf Z}}
\def\T{\top}
\def\true{\top}
\def\false{\bot}
\def\F{\bot}
\def\iff{\leftrightarrow}
\def\underline#1{{\bf #1}}
\def\notequal{\not=}
\def\plusminus{\pm}
\def\circle{\circ}
\def\N{{\rm\bf N}}
\def\Z{{\rm\bf Z}}
\def\R{{\rm\bf R}}
\def\Q{{\rm\bf Q}}
\def\C{{\rm\bf C}}
\def\page{\vfill\eject}
\def\title#1{\centerline{\bigrm #1}\bigskip}

\def\author#1{\centerline{\bf #1}\par}
\def\department#1{\centerline{#1}\par}
\def\university#1{\centerline{#1}\par}
\def\address#1{\centerline{#1}\par}

\def\by#1#2#3#4{\author{#1}\department{#2}\university{#3}\address{#4}
                \bigskip}
\def\({\left (}
\def\){\right )}
\def\[{\left [}
\def\]{\right ]}
\def\lf{\left\lfloor}
\def\rf{\right\rfloor}
\def\lc{\left\lceil}
\def\rc{\right\rceil}

\magnification=\magstep1
\def\mod{{\rm\ mod\ }}
\nopagenumbers

\centerline{\bigrm Ramsey Numbers}
\medskip

Your goal is to find some Ramsey numbers $R(m,n)$.  Part of your effort
will be to compute Ramsey numbers while the rest will be to look up some
established Ramsey numbers.  You are to use some high tech information
resources and the traditional part of the library to help you
find the required information.

\item{1.}Show that the Ramsey number $R(3,4)$ is 9.  You may use facts
         proved in class.
\item{2.}Consider the graph $G$ given by $V(G)=\{0,1,2,3,\cdots ,16\}$
         and $E(G)=\{ab| a-b \equiv 1,2,4,8,9,13,15,16 \mod 17\}$.
  \itemitem{a.}Show that the function $f(x)\equiv x+c \mod 17$ is a
               graph automorphism for any integer $c$.
  \itemitem{b.}Show that multiplication by 2 modulo 17 is an
               automorphism.
  \itemitem{c.}Show that if $G$ contains a $K_4$ then $G$ has a $K_4$
               which includes vertices 0 and 1.  Then show that $G$
               contains no $K_4$.
  \itemitem{d.}Show that $G$ is self complementary. (Hint: look for an
               isomorphism similar to the one in part b.)
  \itemitem{e.}Prove that $R(4,4)=18$.

\item{3.}Learn how to access the World Wide Web and use it to find the
         Electronic Journal of Combinatorics.  When you find the journal
         on the computer browse the journal until you find the survey
         article on small Ramsey numbers.  Download this article and
         print it.  You will use it for the remainder of the project.
\item{4.}Take some time browsing the article.  Describe some of the
         variations on Ramsey's numbers the article surveys.  What are
         the known values of multicolor classical Ramsey numbers.  How
         many papers are listed in the References?  What do * and **
         mean when next to a reference?
\item{3.}Find the tables of the known classical two color
         Ramsey numbers and the references of where to find them.
  \itemitem{a.}How do the known values and bounds for $R(3,n)$ compare
               with the bounds established in class?  You may wish to
               plot a graph to illustrate how close the bounds are.
  \itemitem{b.}According to the table, what is the lowest value of $n$
               for which $R(n,n)$ is unknown?
  \itemitem{c.}According to the table, what is the largest value for $n$
               for which $R(4,n)$ is known?
\item{4.}Next find the paper in the library which establishes $R(3,8)$.
         Make a copy of the paper and read it. (There may be parts which
         you do not understand completely, but that is OK.)
         Give a summary of what was
         done in the paper.  Be sure to indicate the bounds
         on $R(3,8)$ before this paper was published and who determined
         these bounds.
\item{5.}The paper in part 4) is by two authors.  One of the authors is
         from Australia.  Go back to the Web and find the home page for
         the Australian author's univesity.  If you browse the pages for
         his or her university you will find a picture of this author.
         In the picture is
         another Ramsey number.  What is that number?
\bye
