{"id":33,"date":"2020-06-12T16:02:22","date_gmt":"2020-06-12T20:02:22","guid":{"rendered":"http:\/\/sites.nd.edu\/ramsey-theory-2020\/?p=33"},"modified":"2020-06-13T17:15:01","modified_gmt":"2020-06-13T21:15:01","slug":"tuesday-of-week-2-red-group","status":"publish","type":"post","link":"https:\/\/sites.nd.edu\/ramsey-theory-2020\/2020\/06\/12\/tuesday-of-week-2-red-group\/","title":{"rendered":"Tuesday of week 2, red group"},"content":{"rendered":"<p>Here&#8217;s the plan for Tuesday, June 16, for the <strong><span style=\"color: #ff0000\">Red<\/span><\/strong> group:<\/p>\n<ul>\n<li><strong>Everyone<\/strong>:<br \/>\n* Re-read the proof of Theorem 1.16 &#8212; the basic proof strategy will re-appear in later proofs of more expansive Ramsey-type theorems. It will be very helpful to start the proof by taking (with hindsight) \\(N=2^{2k}\\); that way, once you have (once) verified that \\(\\lceil (2^m-1)\/2 \\rceil = 2^{m-1}\\) for any natural number \\(m\\), you get to avoid all the messy algebra at the end of the proof.<br \/>\n* Do exercise 1.18 (which is essentially the Bolzano-Weierstrass theorem for finite sequences).<br \/>\n* Think about the following much harder variant of exercise 1.18: part of that exercise asks you to show that there is a sequence of reals of length \\(k^2\\) that has neither an increasing nor a decreasing subsequence of length \\(k+1\\). Show that this is best possible, that is, show that <em>every<\/em> sequence\u00a0of reals of length \\(k^2+1\\) has either an increasing or a decreasing subsequence of length \\(k+1\\).<br \/>\n* Study the proof of Theorem 1.19 (Ramsey&#8217;s theorem for colouring pairs, with many colors).<br \/>\n* Read Section 1.4, through at least to the proof of Theorem 1.24.<\/li>\n<li><strong>Individual assignments<\/strong>:<br \/>\n* For both parts of exercise 1.18, and the harder variant, I&#8217;ll throw it open to anyone who wants to volunteer ideas.<br \/>\n* Proof of Theorem 1.19 (Ramsey&#8217;s theorem about finding a monochromatic \\(k\\)-clique, when colouring with \\(r\\) colours): <strong>Bailee<\/strong>.<br \/>\n* Exercise 1.20 (Schur&#8217;s theorem, a cute application of Ramsey&#8217;s theorem): <strong>Casey<\/strong>.<br \/>\n* Theorem 1.23 (another proof of Ramsey&#8217;s theorem, that uses &#8220;off-diagonal&#8221; Ramsey numbers): <strong>Colin<\/strong>.<br \/>\n* Theorem 1.24 (getting better upper bounds for Ramsey numbers, using the result of Theorem 1.23): <strong>Greyson<\/strong>. (We may not get to this on Tuesday).<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Here&#8217;s the plan for Tuesday, June 16, for the Red group: Everyone: * Re-read the proof of Theorem 1.16 &#8212; the basic proof strategy will re-appear in later proofs of more expansive Ramsey-type theorems. It will be very helpful to start the proof by taking (with hindsight) ; that way, once you have (once) verified &hellip; <a href=\"https:\/\/sites.nd.edu\/ramsey-theory-2020\/2020\/06\/12\/tuesday-of-week-2-red-group\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Tuesday of week 2, red group<\/span><\/a><\/p>\n","protected":false},"author":3751,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-33","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/sites.nd.edu\/ramsey-theory-2020\/wp-json\/wp\/v2\/posts\/33","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.nd.edu\/ramsey-theory-2020\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.nd.edu\/ramsey-theory-2020\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.nd.edu\/ramsey-theory-2020\/wp-json\/wp\/v2\/users\/3751"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.nd.edu\/ramsey-theory-2020\/wp-json\/wp\/v2\/comments?post=33"}],"version-history":[{"count":4,"href":"https:\/\/sites.nd.edu\/ramsey-theory-2020\/wp-json\/wp\/v2\/posts\/33\/revisions"}],"predecessor-version":[{"id":37,"href":"https:\/\/sites.nd.edu\/ramsey-theory-2020\/wp-json\/wp\/v2\/posts\/33\/revisions\/37"}],"wp:attachment":[{"href":"https:\/\/sites.nd.edu\/ramsey-theory-2020\/wp-json\/wp\/v2\/media?parent=33"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.nd.edu\/ramsey-theory-2020\/wp-json\/wp\/v2\/categories?post=33"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.nd.edu\/ramsey-theory-2020\/wp-json\/wp\/v2\/tags?post=33"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}