3 ms·
A Simple Visual Proof of a Powerful Idea in Graph Theory
- kleiba 9y agoStrictly speaking this "visual proof" is not a proof at all, it's just an illustration of one simple case. But what's good about is that it helps give you an intuition about why Ramsey's theorem is true: namely, that you'd eventually run into a dead-end when trying to color edges, in the sense that you're bound to create a sub-graph where all edges are either colored red or blue.
- nandushines 9y ago"Ramsey’s theorem states that in any graph where all points are connected by either red lines or blue lines, you’re guaranteed to have a large subset of the graph that is completely uniform—that is, either all red or all blue." Can someone please explain how a large subset is defined? I am new to Graph Theory.
- 110011 9y agohttps://en.wikipedia.org/wiki/Induced_subgraph https://en.wikipedia.org/wiki/Induced_subgraph
- Sniffnoy 9y ago"Large subset" is not a technical term. The right question here is not "how is large subset" defined; it's "What does Ramsey's theorem actually state?" A totally abstract version of the theorem would be (note: I'm only considering finite versions of Ramsey's theorem here), Ramsey's theorem states that given any n and m, there's a number R(n,m) such that if you have a complete graph on R(n,m) vertices, and you color each edge red or blue, there's either a uniformly red subset of n vertices or a uniformly blue subset of m vertices. A more useful version would give an example of a number you could pick for R(n,m). (Normally we define R(n,m) to be the smallest such number, so you're giving an upper bound on it.) For instance, Erdos and Szekeres proved that R(n,m)<=(r+s-2 choose r-1).
- DennisP 9y agoThe article says this is a useful tool, but doesn't say why. What's an example of something this is used for?
- air7 9y agoI remember hearing about a social scientist "discovering" that in any classroom he visited, there always seemed to be 4 kids that were either all friends, or were all not friends. He wrote a paper that attempted to explain this using social theory/group dynamics... (This was told by my Discrete math professor when learning about Ramsey's Theorem )