18.217 (FALL 2017): PROBLEM SETS

Problem sets will be due about once every two weeks. You will be asked to hand in a subset of your choosing of specified size from a list of problems. Hand in at most one part from any multipart problem. Each problem has a difficulty factor [d], such as [3-]. This is converted into a weight w(d), as follows:

• w(1-) = 0.1, w(1) = 0.3, w(1+) = 0.5
• w(2-) = 1, w(2) = 2, w(2+) = 3
• w(3-) = 5, w(3) = 8, w(3+) = 12
• w(4-) = 18, w(4) = 25, w(4+) = 50
• w(5-), w(5): depends on solution
Each part will have ten points. Your grade on a problem will be the number of points you receive (out of 10) times the difficulty weight. The weights assume that you solved the problem from scratch. If it appears that you already had some familiarity with the problem, the weight may be reduced.

Problems should be solved primarily on your own. Some "reasonable" collaboration is permitted, but you shouldn't just obtain the solution from another source. Do not hand in a solution that you did not obtain on your own or did not obtain by collaboration with another student in the course! You should also not hand in a problem that you already know how to solve. Also, hand in at most one part of a multipart problem (such as 3.42, which has two parts).

Problem sets can be turned in during class or sent by email to the grader (gaetz@mit.edu) by the beginning of class on the due date.

Problems come from the following sources:

Problem Set 1: EC1, Chapter 3, problems 14, 31(a), 34, 39, 42, 44, 46; additional A1, A2, A3, A4. (A problem number preceded by "A" is an additional problem.) Problem 3.14(a) will be given the weight 4, since it seems somewhat harder than a typical 2+ problem. Problem 3.14(b) is for those familiar with the terminology or willing to look it up. In regard to Problem 3.39, the definition of finitary distributive lattice in the text is incorrect. See the errata (item for page 253) for the correct definition. Hand in your "best" five problems by the end of class on Monday, September 18.

Problem Set 2: EC1, Chapter 3, problems 45(a), 52, 53, 54, 57, 58, 60(a,c); additional A5, A6. Hand in your best four problems by the end of class on Monday, October 2.

Problem Set 3: EC1, Chapter 3, problems 85, 89, 90, 91, 98, 99, 100(d), 114; additional A10. Hand in your best four problems by the end of class on Monday, October 16. No further problems are forthcoming. Note #1. The difficulty rating [3+] of 91(b) assumes that you solve the problem from scratch. If you do it using certain deep outside results, the rating goes down to [3-]. Note #2. At the moment the only solution I know for 100(d) uses some results that have not been covered in class and which a "typical" graduate student wouldn't know. I seem to remember that I once knew a simpler solution. For the time being the difficulty rating is raised to [3], though perhaps this will be downgraded again to [3-] if someone comes up with a simple solution. Note #3. For 3.98 and 3.114(a), note the corrections here.

Problem Set 4: EC1, Chapter 3, problems 62(a-e), 63, 64(a,b), 127(a-c), 128, 129, 134, 144, 148, 167(a), 168; additional A8, A11. No further problems are forthcoming. Hand in your best four problems by the end of class on Friday, October 27. Hint for A11. The crucial property of Uk is that every zero of the Uk-Eulerian polynomial AUk(x) except for x=0 has absolute value 1. Note. In problem A8, change A(2n+1,n+1) to A(2n+1,n). The same correction needs to be made in Exercise 3.53(a).

Problem Set 5: EC1, Chapter 3, problems 3.178, 3.183(e), 3.185(f-i); additional A7, A12, A13, A14, A16, A17. No further problems are forthcoming. Hand in your best four problems by the end of class on Wednesday, November 8. Problem A7(a) has a weight of 4 (between [2+] and [3-] in difficulty). A refinement of Example 3.18.10 may prove useful for A7(a). Problem A13(b) is rated [3]. However, perhaps there is a simpler solution than the one that I know. Note. Problem A16(c) is trivial as stated, so it has been removed.

Problem Set 6: EC1, Chapter 3, problems 3.189, 3.191; additional A9, A18, A19, A20, A21, A22, A23, A24. No further problems are forthcoming. Hand in your best four problems by the end of class on Monday, November 20. However, do at most one of A19 and A20. Note. Problem A19 is not so bad using a difficult exercise in Chapter 3. Is there a simpler solution avoiding this exercise? It is okay to use the result of A20 in a solution to A19. Note. Problem A9 was originally stated incorrectly. It was corrected on November 8. Note. Problem A16(c) (part of Problem Set 5) is trivial as stated, so it has been removed. Note. It seems to me that Exercise 3.189 might be much weaker than possible. Possibly for any d≥2, there is a unique (up to isomorphism) Eulerian poset P of rank d+1 and with d atoms, such that P-{1} is simplicial. Can anyone prove this? It might not be so difficult. Update. Actually, it is false. Exercise 3.189 seems reasonable, but the difficulty rating [2+] seems too low to me (unless I have forgotten a simpler argument), so it now is rated [3-]. The result of this exercise is also true when d is odd, but the proof is much easier. Updated update. Christian Gaetz found a [2+] level solution to 3.189 which is probably what I had in mind when I chose the [2+] rating, so the rating is now downgraded back to [2+]. As a continuation of 3.189, I have added A23, with a weight of 4 (difficulty rating between [2+] and [3-]). Do at most one of 3.189 and A23.

Problem Set 7: EC1, Chapter 3, problems 3.211, 3.212, 3.215(b); additional A25, A26, A27. Hand in your best four problems by Monday, December 4. No further problems are forthcoming. Sadly, this is the final required pset. Be sure to take a look at the EC1 errata before working on 3.211.

Self problems: due by the end of class on Monday, December 11. At the course Home Page the following is stated: you should hand in two problems of your own with difficulty ratings and solutions. They should be related to partially ordered sets. I certainly don't expect them to be publishable in general. Grading of these "self problems" will be based more on elegance, originality, and pedagogical value than on difficulty. The self problems count 20% of the course grade.

Problem Set 8: hand in all problems from Chapter 3 not previously assigned, without looking at the solutions. No due date, and no affect on the course grade, but a good way to learn more about posets.