Coordinates. WIS, Semester B, Sundays, 16:00-17:45 (with a break), Room 261.
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:
First lecture's assignment.
Graders: Neta Atzmon and Gil Goffer.
Second lecture's assignment. There are two options for this assignment:
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:
Graders: Myriam Goor and Jonathan Rosenskii.
Fourth lecture's assignment.
Due: Wednesday, 23.4, 12:00, in my mailbox.
Graders: Ayelet Gottlieb and Anna Hoffmann.
Fifth lecture's assignment.
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
a_{1}, a_{2},... in S such that the intersection of all sets
FP(a_{n}, a_{n+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.
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.
Due: Monday, 12.5, 12:00, in the envelope in my mailbox.
Graders: Yaron Harel and Sigal Rotem.
Seventh lecture's assignment.
Due: Monday, 26.5, 12:00, in the envelope in my mailbox.
Graders: Neta Atzmon and Gil Goffer.
Eighth lecture's assignment.
Due: Monday, 2.6, 12:00, in the envelope in my mailbox.
Grader: Alexander Shamov.
Ninth lecture's assignment.
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.
Graders: Lubna and Aviv.
Tenth lecture's assignment.
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 S_{1}(F) be the statement: For all A_{1},A_{2},... in F, there are elements a_{1} in A_{1}, a_{2} in A_{2}, ..., such that the set {a_{1},a_{2},...} is in F.
Prove: There are:
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.
Grader: Boaz.
Equidist: A new game.
Thanks to the following colleagues and students for their corrections and useful suggestions for the course book: Eran Alouf, Ran Cohen, Gili Golan, Yuval Hachatrian, Barak Harel, Yaron Harel, Yonatan Hermon, Noam Kakhlon, Moshe Lebovich, Noam Levin, Noam Lifshitz, Michael Machura, Adam Netanel, Eviatar Parker, Asher Patinkin, Luie Polev, Motke Porrat, Itay Ravia, Alexander Shamov, Meny Schlossberg, Ohad Zohar, Shoval Zoran.
(c) All rights reserved to Boaz Tsaban.