Combinatorial Number Theory (or: Ramsey Theory)

Wednesdays 14:00-16:00, Ziskind 1.

Important notice! If you are not in the course's mailing list, please let me know immediately (email me your email address which you use most frequently). Important announcements (like errors in exercises, cancellation of a lecture, etc.) will be emailed only to the mailing list.

Exercises

A probabilistic-like proof of Ramsey's Theorem: See Theorem 2 there and its elegant proof.

Language. Exercises must be written in English.

1. 16 Jul 07:
   • Read the file in the link, upto Theorem 2.3 not including it, and then from 2.6 to the end.
   • Solve 3 out of the following 4 questions: 1,6 on page 13, and 1,2 on page 19.
   Gal's comment to question 3 on page 19: The hint seems wrong but the claim itself is still easy to prove, and I think it might be a bit interesting. It uses the same "paradoxical decomposition" of the free group that gives the Banach-Tarski "paradox". Let F_x be all the words whose reduced description starts with x (for x=a,b,a^-1,b^-1). Then (x^-1)F_x = F \setminus F_{x^-1}. So a left-translate of F_x is essentially a union of three of the four F_y's. A simple comparison argument shows that you can't have an invariant measure with this property.

2. 30 Jul 08:
   • Read the file in the link (parts not taught in the lecture are not mandatory, but nice to have).
   • Solve questions 2,4 on the last page of that file.
   Solution of question 5 (of the same page).

3. 6 Aug 08:
   • Read the file in the link "Solution of question 5" above.
   • Read the file in the link "6 Aug 08" above.
   • Solve questions 2,3(assume X is infinite!),4,5(prove that Y contains an infinite uniformly discrete set), on the last page of this file.
4. 13 Aug 08:
   • We were quite close: Read the full proof.
   • Read the file in the link "13 Aug 08" above.
   • Solve questions 1,3 on the last page of this file.
5. 20 Aug 08:
   • Read the file in the link.
   • Solve questions 1,2,3 on the last page of this file.
   • Note that the sets A_n in Q.1 must be nonempty for the question to make sense.
6. 27 Aug 08:
   • Read the file in the link (including the application to high-dimensional tic-tac-toe).
   • Solve questions 1,2,3.
7. 3 Sep 08: Solve as many as you can of the following.
   • Find a coloring of N with as few colors as you can, such that x+y-3z=0 has no monochromatic solution.
   • Complete the details in the ultrafilter-proof that for each coloring of N and all natural m, there is a monochromatic sequence of the form d;a,a+d,...,a+md.
   • Challenge: Find a proof using Stone-Chech compactifications, of the assertion: For each coloring of N and all natural s,m, there is a monochromatic sequence of the form sd;a,a+d,...,a+md. (i.e., get (2) for general s.)
8. 10 Sep 08:
   • Read the file in the link.
   • Solve the following exercise.
9. 17 Sep 08: Concluding exercise.
   • Read what you didn't read in the file in the link.
   • Solve Questions 1,2 at its end.
   • Read the last chapter, and solve Questions 1,2 at its end.

Shana Tova Umetuka,

Boaz