Ramsey Theory  


Time:   Thursdays 13:45-15:15 and 15:30-17:00
Place:   A2-3.
Instructor:   Tomasz Łuczak
Textbooks:   The course is based on the standard monograph for this subject: R.L.Graham, B.L.Rothschild, and J.H.Spencer, "Ramsey Theory", Wiley, 1990. To learn about random and pseudorandom structures, one may want to look at the book N.Alon and J.H. Spencer "The probabilistic method" Wiley, New York 2000, and T. Łuczak, "Random and pseudo-random structures", Centre de Recerca Matematica Bellaterra, 2007.



Homework assignments:
  Homework I      due to May 17
  Homework II     due to May 31
Comment: I have heard a rumour that some of you try to apply rather sophisticated tools to do HA2. Well, it is really not so hard, since we deal with vertex colourings which are much easier to handle than edge colourings. Prove first that for every 2-connected H there exists G which arrows H for vertex coloring such that each copy of H in G is induced, and then try to find out how to show that there exists G arrowing H which is even "H-copy sparser".
The final hint: Show first that for every g, k, and r, there exists a family F of k-elements subsets of some set V such that F contains no "cycles" of length smaller than g yet any coloring of the elements of V with r colors leads to a monochromatic set from this F.
  Homework III     due to June 8
  Homework IV     due to June 14