Third Exam: Ramsey Theory
Ugh. And can I say ugh again? I have to prepare for two more exams tomorrow, and one more the day after (that I'm woefully underprepared for... but everyone seems to be), and I have no energy. Hopefully reading blogs will help, but if it doesn't...
I've also been unable to sleep for the last couple of days. I keep starting awake, certain that I've missed a day and I've skipped some exams and I'm going to fail and MIT will reject me and badness will ensue. And yes, I know that I have nothing to worry about, that I've likely already done enough work to pass and that even if I don't get a distinction that won't be the end of the world (or even the end of anything, other than my year at Cambridge (and that will come anyway)), and that really I shouldn't be worried. Like any of that helps. Ha. I think that stress is contagious: because some of the students are really worried (as the exams MATTER to them, since Ph.D. spots are given based on exam results) everyone else picks it up. Not that thinking that helps, either.
Anyway, the exam today was for Ramsey theory. 3 of 4 questions to solve, 2 hours. I didn't expect it to be so stressful, because unlike my previous exams there was NOT enough time. The exam was maybe a little bit shorter than both algebraic topology and category theory, but a whole hour shorter. And I wrote more than I wrote for either of those exams. (One of my solutions was 3 pages long, another 2 and a half.) The questions were:
1. (i) Using Ramsey's theorem, show that whenever N is finitely colored there exist x_1<x_2<... such that the set {x_i + x_j | i != j} is finitely colored. This was easy; it was a 3-line solution only because I insisted on justifying everything.
(ii) Show that whenever N is finitely colored there exist x_1<x_2<... such tha the set {x_i + 2x_j | i < j} is monochromatic. This was even easier.
(iii) Show that it is not true that whenver N is finitely colored there exist x_1<x_2<... such that the set {x_i + 2x_j | i != j} is monochromatic. I didn't solve this. Neither did anyone else I talked to. None of the obvious colorings work, and I couldn't really find anything else to do.
(iv) Deduce from (iii) that there is no ultrafilter on N, each member of which contains a set of the form {x_i + 2x_j | i != j}. Also really easy.
2. State and prove van der Waerden's theorem. Deduce that, if a_1,...,a_n are nonzero rationals then the matrix (a_1 ... a_n) is partition regular iff some (non-empty) subset of the a_i has sum 0. This was just incredibly annoying. Both of the parts have long proofs, neither of which has many ideas. This was my 3 page solution, and it was the most annoying thing ever. I think the prof doesn't like bookwork (yay him!) so he gives annoying bookwork problems. (Bookwork is reproducing proofs given in lecture.)
3. [Long annoying problem about ultrafilters. Easy, but long and I didn't want to write as much as I did in problem 2, so I skipped it.]
4. What does it mean to say that a subset of N^(omega) is Ramsey? Give an example of a set that is not Ramsey. Prove that every tau-open set is Ramsey.
Find, with justification, examples of each of the following:
(i) a set that is *-open but not tau-open
(ii) a set that is tau-nowhere-dense but not *-nowhere-dense
(iii) a set that is *-nowhere-dense but not tau-nowhere-dense
This problem was annoying. And part (iii) was hard; it took me half an hour. Which on a two-hour exam is a LOT. Especially for a quarter of a problem. And did I mention annoying?
Anyway, now I'm going to go veg for a while. And then study. And then try to sleep. (Maybe I'll do those in another order...)
I've also been unable to sleep for the last couple of days. I keep starting awake, certain that I've missed a day and I've skipped some exams and I'm going to fail and MIT will reject me and badness will ensue. And yes, I know that I have nothing to worry about, that I've likely already done enough work to pass and that even if I don't get a distinction that won't be the end of the world (or even the end of anything, other than my year at Cambridge (and that will come anyway)), and that really I shouldn't be worried. Like any of that helps. Ha. I think that stress is contagious: because some of the students are really worried (as the exams MATTER to them, since Ph.D. spots are given based on exam results) everyone else picks it up. Not that thinking that helps, either.
Anyway, the exam today was for Ramsey theory. 3 of 4 questions to solve, 2 hours. I didn't expect it to be so stressful, because unlike my previous exams there was NOT enough time. The exam was maybe a little bit shorter than both algebraic topology and category theory, but a whole hour shorter. And I wrote more than I wrote for either of those exams. (One of my solutions was 3 pages long, another 2 and a half.) The questions were:
1. (i) Using Ramsey's theorem, show that whenever N is finitely colored there exist x_1<x_2<... such that the set {x_i + x_j | i != j} is finitely colored. This was easy; it was a 3-line solution only because I insisted on justifying everything.
(ii) Show that whenever N is finitely colored there exist x_1<x_2<... such tha the set {x_i + 2x_j | i < j} is monochromatic. This was even easier.
(iii) Show that it is not true that whenver N is finitely colored there exist x_1<x_2<... such that the set {x_i + 2x_j | i != j} is monochromatic. I didn't solve this. Neither did anyone else I talked to. None of the obvious colorings work, and I couldn't really find anything else to do.
(iv) Deduce from (iii) that there is no ultrafilter on N, each member of which contains a set of the form {x_i + 2x_j | i != j}. Also really easy.
2. State and prove van der Waerden's theorem. Deduce that, if a_1,...,a_n are nonzero rationals then the matrix (a_1 ... a_n) is partition regular iff some (non-empty) subset of the a_i has sum 0. This was just incredibly annoying. Both of the parts have long proofs, neither of which has many ideas. This was my 3 page solution, and it was the most annoying thing ever. I think the prof doesn't like bookwork (yay him!) so he gives annoying bookwork problems. (Bookwork is reproducing proofs given in lecture.)
3. [Long annoying problem about ultrafilters. Easy, but long and I didn't want to write as much as I did in problem 2, so I skipped it.]
4. What does it mean to say that a subset of N^(omega) is Ramsey? Give an example of a set that is not Ramsey. Prove that every tau-open set is Ramsey.
Find, with justification, examples of each of the following:
(i) a set that is *-open but not tau-open
(ii) a set that is tau-nowhere-dense but not *-nowhere-dense
(iii) a set that is *-nowhere-dense but not tau-nowhere-dense
This problem was annoying. And part (iii) was hard; it took me half an hour. Which on a two-hour exam is a LOT. Especially for a quarter of a problem. And did I mention annoying?
Anyway, now I'm going to go veg for a while. And then study. And then try to sleep. (Maybe I'll do those in another order...)
posted by Inna | 8:00 AM
1 Comments:
1. (iii) Color n according to the first digit after the decimal point of log_10(n). For any x, and any y > 100x, say, the numbers 2x+y and x+2y have different colors (proof below). So there are no infinite monochromatic subsets.
Proof of claim: Say y has color a; then 2x+y has color a or a+1, whereas (since 0.3 < log_10(2) < 0.4) x+2y has color a+3 or a+4 or a+5 (a+5 is not really possible).
Reid
Post a Comment
<< Home