3 ms·

His proof of Ramsey's Theorem [0] is possibly my favorite proof of all time. [0] https://en.wikipedia.org/wiki/Ramsey%27s_theorem https://en.wikipedia.org/wiki

His proof of Ramsey's Theorem [0] is possibly my favorite proof of all time. [0] https://en.wikipedia.org/wiki/Ramsey%27s_theorem https://en.wikipedia.org/wiki/Ramsey%27s_theorem

millstone 7y ago
What is it you like about the proof?
- eindiran 7y ago
  There is a section that uses the same type of thinking that you can use to prove the R(3, 3) = 6 case (often known as the Theorem of Friends and Strangers [0]), towards the end of the paper [1] (though in a pretty different way). Proving the general case of things is often very removed from the proofs of a specific case, so its interesting to see similar thinking in the general case. Also, I really like the simplicity of the proof of the Theorem of Friends and Strangers. You can show someone the proof with two colored pens in 10 minutes. But at the same time, it uses some interesting proof tools: contradiction, the pidgeonhole principle, creating a boundary by counterexample (ie that R(3, 3) must be greater than 5). So I like the Friends and Strangers proof for its elegance and how fun it is to show people, and I like Ramsey's proof because it captures some of the fun of the R(3, 3) case while proving something much, much more difficult. [0] https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers https://en.wikipedia.org/wiki/Theorem_on_friends_and_strange... [1] https://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseyorig.pdf https://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseyorig.pdf
bitL 7y ago
It was pretty mind-blowing to realize during a discrete math class that chaos is basically impossible. Then learning that Ramsey passed away very young felt terrible.
- Y_Y 7y ago
  Not to mention that thermodynamics and classical/quantum mechanics mean that in our world chaos is basically inevitable.
- wtallis 7y ago
  I'm not sure I'd interpret that result as "chaos is impossible". I'd rather say that you can always find some apparent pattern (of smallish size) by searching through enough randomness/chaos. That seems intuitively to be fairly unsurprising considering everyday experiences like cloud gazing, or the existence of conspiracy theorists. Whether the pattern you find has any important meaning is an entirely different question.
  - eindiran 7y ago
    I think a reasonable interpretation of the result is the idea that all "chaotic" graphs of sufficient size _must_ contain order, which isn't as strong as "chaos is impossible", but isn't very intuitive to me.

His proof of Ramsey's Theorem [0] is possibly my favorite proof of all time. [0] https://en.wikipedia.org/wiki/Ramsey%27s_theorem https://en.wikipedia.org/wiki/Ramsey%27s_theorem

millstone 7y ago

What is it you like about the proof?

eindiran 7y ago
There is a section that uses the same type of thinking that you can use to prove the R(3, 3) = 6 case (often known as the Theorem of Friends and Strangers [0]), towards the end of the paper [1] (though in a pretty different way). Proving the general case of things is often very removed from the proofs of a specific case, so its interesting to see similar thinking in the general case. Also, I really like the simplicity of the proof of the Theorem of Friends and Strangers. You can show someone the proof with two colored pens in 10 minutes. But at the same time, it uses some interesting proof tools: contradiction, the pidgeonhole principle, creating a boundary by counterexample (ie that R(3, 3) must be greater than 5). So I like the Friends and Strangers proof for its elegance and how fun it is to show people, and I like Ramsey's proof because it captures some of the fun of the R(3, 3) case while proving something much, much more difficult. [0] https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers https://en.wikipedia.org/wiki/Theorem_on_friends_and_strange... [1] https://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseyorig.pdf https://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseyorig.pdf

bitL 7y ago

It was pretty mind-blowing to realize during a discrete math class that chaos is basically impossible. Then learning that Ramsey passed away very young felt terrible.

Y_Y 7y ago
Not to mention that thermodynamics and classical/quantum mechanics mean that in our world chaos is basically inevitable.
wtallis 7y ago
I'm not sure I'd interpret that result as "chaos is impossible". I'd rather say that you can always find some apparent pattern (of smallish size) by searching through enough randomness/chaos. That seems intuitively to be fairly unsurprising considering everyday experiences like cloud gazing, or the existence of conspiracy theorists. Whether the pattern you find has any important meaning is an entirely different question.
- eindiran 7y ago
  I think a reasonable interpretation of the result is the idea that all "chaotic" graphs of sufficient size _must_ contain order, which isn't as strong as "chaos is impossible", but isn't very intuitive to me.