Projects and Assignments in Pure Mathematics
Ramsey Theory
This is really a topic in combinatorics, but has connections to logic (e.g. set theory), number theory, and
other subjects. An easy (infinitary) version of the theorem says that any infinite graph contains either an infinite
set of vertices
any two of which are joined by an edge, or an infinite set of vertices no two of which are joined by an edge. There are
many subtle variants of this: working with different infinite cardinals,
statements about `monochromatic' arithmetic progressions for colourings of natural numbers, calculation of
bounds for finite versions of Ramsey's Theorem, versions for vector space sover finite fields,
connections to Goedel's incompleteness.
Books
P.J. Cameron, Combinatorics. Topics, techniques, algorithms, Cambridge Univ. Press 1994.
R.L. Graham, B.L. Rothschild, J. Spencer, Ramsey Theory, Wiley, 1990.
Pure projects homepage