Ramsey's Theorem shows complete disorder is impossible | Hacker News Reader

Ramsey's Theorem shows complete disorder is impossible

math.grin.edu

58 pointsColinWright9 comments

This is a sensationalist headline. Ramsey's theorem concerns patterns in a simple system, the coloring of edges in a graph. It says regardless of how the graph is colored you can always find a triangle of vertices with certain properties.

This does not mean complete disorder is impossible. It's just a combinatorial argument that says this simple game of coloring edges on a graph has some patterns to it.

But then maybe you're of the mindset that the universe is a complete graph and physics is a color by number game...in which case....oh god, we're all screwed...

There is an infinite version of Ramsey's theorem.

Suppose you consider the collection of pairs of positive whole numbers, and each pair is colored either red or blue. Then there is an infinite set S of positive whole numbers such that any pair of items from S are the same color.

In symbols:

P = { (a,b) : a in N, b in N }

C : P -> {0,1}

There exists S an infinite subset of N and c in {0,1} such that for all a in S and b in S, C(a,b)=c.

The proof is quite simple, I use it regularly to boggle 13 and 14 year olds.

I figured out the proof on my drive in to work. It is simple.

At all points we're going to have an infinite set of integers to process, a clique of integers whose connections to each other and all of the integers left to process is red, and a clique of integers whose connections to each other and all of the integers left to process is blue. (red clique, blue clique)

We start with all of N as our set, and our cliques are empty sets.

At each point we take the first thing in our set, and remove it from the set. If there are an infinite number of things left in our set that it has a red connection to, then put it into the red clique and remove all things from the set that its connection is blue to. Else put it into the blue clique and remove all things from the set that its connection is red to. This step can always be done and leaves us with 2 cliques (one of which grew by one) and an infinite set of integers to process.

After we do this an infinite number of times at least one of the red and blue cliques must now be infinite in size. And we're done.

That's an elegant way to express it - thank you. My method has more of the "TA DA!" about it, and tends to generate a sense of "Gosh!", but I like the quiet elegance of yours.

Nice one.

I don't know if Ramsey's theorem really says anything as grand about disorder as Maxwell's demon and the like, but it does express something quantitative about the existence of subsets containing some specific properties as the size of the graph increases.

For me, Ramsey's theory is particularly interesting its rare that an open problem in mathematics can be explained to anyone with relatively little background in mathematics or logic for that matter. Mathematicians have discovered some bounds on R(n), but an exact solution looks like its no where in sight.

Rainbow Ramsey's theorem shows that complete disorder is unavoidable as well. :)

In other words, when complete disorder is achieved, complete order is formed (since that disorder becomes completly homogeneous).

“You know the thing about chaos? It's fair.” - The Joker

what you talking about is exactly the black hole entropy - the maximum entropy achiveable, which is suprisingly not that _big_, i.e. it happens to be proportional to the surface area, not to the volume - the "Bekenstein-Hawking" limit :

http://en.wikipedia.org/wiki/Black_hole_thermodynamics#Black...

Reply on news.ycombinator.com