Combinatorial Number Theory

# Combinatorial Number Theory (Ramsey Theory)

Coordinates. WIS, Semester B, Sundays, 16:00-17:45 (with a break), Room 261.

## The course book

Detailed chapters of the course book will be posted here as the course progresses. It is recommended not to download the material but to read it directly from here, since the material will be constantly corrected and improved (with your help, see below).

1. Front Matter: cover page, preface.
2. Chapter 1: Lecture 1.
3. Chapter 2: Sections 1-2 cover Lecture 2. The remainder covers Lecture 3.
4. Chapter 3: Lecture 4 and most of Lecture 5.
5. Chapter 4: end of Lecture 5 and all of Lecture 6.
6. Chapter 5: Lecture 7.
7. Chapter 6: Lecture 8.
8. Chapter 7: Lecture 9.
9. Chapter 8: Lecture 10.

## Homework

Homework assignments will be posted here soon after every lecture, and are due next lecture. The assignments consist of solutions of an exercises component and a (bonus) proofreading component. It is not mandatory to solve all exercises in each assignment.

The proofreading component will add at most 5% to the final grade, and will be graded separately. It includes reading the relevant material and suggesting corrections of typographic, grammatical, and mathematical errors as well as suggestions for improvements (if applicable). (Particularly helpful students would be acknowledged at the end of this page.)

The assignments will be checked as follows:

1. Eeach week, in rotation, two students will check the assignments, write comments, and provide a grade.
2. The grade will not be out of 100, but rather one of three categories: C (fail), B (ok), A (excellent), and A+ (exceptional). A+ should really mean exceptional. Excessive use (say, more than 10%) of this grade would request a re-grading.
3. The exercise assignment should be graded separately from the proofreading assignment.
4. Each of the two graders will check about half of the questions, across all assignments handed.
5. The graders will not hand out their own assignment. Their grade will be determined by the lecturer, according to the quality of their checking, commenting, and grading.
6. The graders will collect the proofreading comments into a single file (deciding among contradicting suggestions, possibly by consulting those suggesting them) and hand to the lecturer.
7. The graders will hand everything to the lecturer in the day of the lecture the latest. The lecturer will, after examination, put them in his mailbox for distribution. (Expected: Mondays.)
A special exception may be given to students who prove something substantially new along the lines of this field. In particular, students solving problems that I pose as open may be exempted from all exercises and obtain the maximal course grade. Contact me if/when you think you may fall in this category.

First lecture's assignment.

1. (Proof)Read Chaper 1 (see above).
2. Solve Exercises 1.4, 3.6, 3.8, 4.1.

Graders: Neta Atzmon and Gil Goffer.

Second lecture's assignment. There are two options for this assignment:

1. First option:
• (Proof)Read Chaper 2, Sections 1-2 (see above).
• Solve Exercises 1.7, 1.14, 2.2.
2. Second option: Solve the follwing challenge and email your solution directly to me:
• Challenge 1. Find an elementary proof for Theorem 2.1 (in Chapter 2, the Full Compactness Theorem).

Update: This option is half-closed: Alexander Shamov proved that Theorem 2.1 (Full Compactness) is equivalent to the theorem that every filter extends to an ultrafilter (UFT). (Details available here.) This is a (weaker) form of the Axiom of Choice.
The new version of the book presents, instead of the original proof, a proof that is quite elementary modulo knowing what are ordinal and cardinal numbers. I think this practically closes the challenge, even if not in an optimal manner.
Disclaimer: This discussion is completely off the main course of our course. Do not worry if you do not know what I am talking about. Future challenges (usually also off the main course) may touch other fields of mathematics and could equally be ignored at your will.

Graders: Lubna Abu-Rmaileh and Aviv Eshed.

Third lecture's assignment. There are two options for this assignment:

1. First option:
• (Proof)Read Chaper 2, Sections 3-6 (see above).
• Solve Exercises 3.15, 3.16, 4.5, 4.11.
2. Second option: Solve Challenge 1 above (see update there).

Graders: Myriam Goor and Jonathan Rosenskii.

Fourth lecture's assignment.

2. Solve Exercises 1.3(a,b,d), 1.4, 1.9, 3.5.

Due: Wednesday, 23.4, 12:00, in my mailbox.

Graders: Ayelet Gottlieb and Anna Hoffmann.

Fifth lecture's assignment.

1. First option:
• (Proof)Read Chaper 3 (from the paragraph preceding Definition 4.5 on page 24 to the end of the section) and the available part of Chapter 4.
• Solve Exercises 4.8, 5.2, 6.8 in Chapter 3 and Exercise 1.4 in Chapter 4.
• Read the following Problem, the discussion there, and the answer. If anything there is unclear, post your question as a comment there and it will be answered. (You may wish to create a MathOverflow user, but I think you can post questions even without being a user.)
2. Second option: Solve any of the following two challenge problems

Challenge 2: Often, more general theorems are easier to prove. The reason is that by abstracting out unnecessary properties, our attention is focused on the relevant ones. Could it be that the following general Finite Products Theorem proved in Chapter 4 has a digestible elementary proof?

Theorem. For each moving semigroup S, every finite coloring of S has a monochromatic FP set.

The challenge is to discover such a proof. It may be a very hard challenge, or it may lead to a more general (than just containing a moving semigroup) assumption that may, in turn, lead to a relatively simple elementary proof. It would probably be a noteworthy (and definitely publishable--unless this was solved already) achievment to solve this challenge. You may wish to consult Baumgartner's elementary proof of Hindman's Theorem for inspiration, and do some web search first.
Update: It may be better to assume, instead of "moving", that there are elements a1, a2,... in S such that the intersection of all sets FP(an, an+1,...) for all natural numbers n is empty. This assumption is more general than assuming the semigroup contains a moving semigroup (subchallenge: find an elementary proof for the last assertion).

Challenge 3: Find a characterization, in terms of properties of the semigroup S, of the property there is a nonprincipal idempotent in β(S)\S.

Update: Challenge 3 was solved by Neil Hindman and me. The solution will hopefully be added to the book at some point.

Challenge 3 is not completely defined, but both you and I are likely to recognize a good solution if you find one. The idea is to have something like the characterization "S is moving" for "beta(S)\S is a semigroup".

Due: Wednesday, 7.5, 12:00, in the envelope in my mailbox.

Graders: Or Dagmi and Asher Patinkin.

Sixth lecture's assignment.

1. First option:
• Solve Exercises 1.10, 2.4, 3.4, 3.8.
2. Second option: Solve any of the above challenges, or the following one.

Challenge 4. Let N be the additive semigroup of natural numbers. Is the semigroup β(N)\N moving? Does it contain a moving subsemigroup?
Update: Second part solved by Alexander Shamov, in the positive.

A positive answer to either question would imply a Hindman Theorem for nonprincipal ultrafilters.

Due: Monday, 12.5, 12:00, in the envelope in my mailbox.

Graders: Yaron Harel and Sigal Rotem.

Seventh lecture's assignment.

1. First option:
• Solve Exercises 1.9, 2.6, 2.12.
2. Second option: Make progress on any of the above challenges.

Due: Monday, 26.5, 12:00, in the envelope in my mailbox.

Graders: Neta Atzmon and Gil Goffer.

Eighth lecture's assignment.

1. First option:
• Solve Exercises 2.1, 2.4, 2.6, 2.7.
2. Second option: Make progress on any of the above unsolved challenges.

Due: Monday, 2.6, 12:00, in the envelope in my mailbox.

Ninth lecture's assignment.

1. First option:
• Solve Exercises 1.3, 2.5, 3.6.
2. Second option: Obviously, Schur's equation x+y-z=0 has a solution x,y,z in A for every FS set A.

Challenge 5: Characterize the linear homogeneous equations with integer coefficients that have solutions in every FS set A.

Due: Monday, 9.6, 12:00, in the envelope in my mailbox.

Tenth lecture's assignment.

1. First option:
• Solve Exercises 2.3, 2.8.
2. Second option: Make progress on a challenge.

Due: Monday, 16.6, 12:00, in the envelope in my mailbox.

Graders: Myriam Goor and Jonathan Rosenskii.

Final Assignment

The role of this assignment is to demonstrate your ability to come up with, and consider, problems of the nature studied in the course. A starting point may be any of the yet unsolved challenges posted above or below. You may also read and use any related literature. In particular, you may consider the book of Hindman and Strauss - some of the problems you come up with may be solved. It is fine not to consider outside literature if you do not wish to do so.

Summarize your attacks on the problems, alternative problems you tried, and if unsuccessful, what where the obstacles. You may begin with easy variations of the problems you are considering, and make them harder until you fail to solve them (write down which variations you tried, ordered from easy to hard, and sketch the solutions for those you solved). Write down any insight that came to you during your concentrated efforts.

You may discuss matters in groups, but write separately. The assignments should not exceed 4 pages of text, unless you see a clear need (in such a case, provide a brief explanation at the beginning why you needed more than 4 pages).

The weight of this assignment (and the estimated time needed for it) is equivalent to that of two earlier assignments.

Challenge 6: We begin with some definitions. A family F of sets is partition regular if, for each A in F and each partition A=B U C, we have that B is in F or C is in F.

Let S1(F) be the statement: For all A1,A2,... in F, there are elements a1 in A1, a2 in A2, ..., such that the set {a1,a2,...} is in F.

Prove: There are:

1. A partition regular family F such that S1(F) holds;
2. A set A in F; and
3. A finite coloring of [A]2,
such that, for each subset B of A with B in F, the set [B]2 is not monochromatic.

Remark: This is posed as Conjecture 1.19 in my paper Superfilters, Ramsey theory, and van der Waerden's Theorem (with N. Samet, an alumni WIS student!), available here. But we didn't think about this. This may be solvable. In that paper, there is a simpler reformulation (you just need to prove that F is not "weakly Ramsey"/"strongly Ramsey", as defined in Definition 1.6 there.)

Due: (Originally, Thursday, 24.7.14.) Due to the war, you may postpone your submission due as much as reasonably needed. Just notify me by mail in case you do so.