Comment by n4r9 | Hacker News Reader

Comment by n4r9 | Hacker News Reader

Parent Full thread

It's hard to know what you're finding uninteresting/confusing from your description. Perhaps it would help to note that every possible pairing is given a colour, and in your infinite subset every possible pairing within that subset has the same colour. To me this is quite counter-intuitive.

There is a somewhat enlightening comparison to be made between Ramsey on pairs and the result that every real sequence x_n has a monotonic subsequence. You get this result as a corollary by colouring a pair of natural numbers a<b red if x_a <= x_b and blue otherwise.

Interestingly, the Ramsey theorem can be extended to three, four or any number of colours. I believe you can use this to show that any real sequence has either a convex or concave subsequence, but I'll omit the details :p

There's also a delicate balance between the infinite and finite going on. Clearly, with an infinite number of colours you could get a colouring without a monochromatic subset. More surprisingly perhaps, if you colour the infinite subsets of the natural numbers red or blue, then there exist colourings for which there is no monochromatic subset.

I have the same confusion as the GP, so let me try to ask a clarifying question:

Is the challenge to partition the pairs (of natural numbers) such that both partitions are infinite and monochromatic? Is that the hard thing that was proved here?

If so, how about "color red if a = b-1, blue otherwise"? Then the infinite subset (0, 1), (1, 2), (2, 3), ... is monochromatic.

What criterion did my partition there fail to satisfy?

The hard part is to show that for any coloring, there's some infinite subset without relying on "well, we can just pick one for each of these infinitely many numbers".

I'm pretty sure that the challenge is to prove that you can for any coloring construct a finitely defined rule for picking the members of the subset which is guaranteed to give you a monochromatic subset.

The question is more about if you can always find such a (finite) rule to partition the set, rather than if you can in a few easily constructed examples.

But it's not true for any coloring, e.g. "red if a and b < 20, blue otherwise".

Wouldn't the subset {(a, b) | a,b > 20} be monochromatic?

Ed:

Perhaps I phrased it poorly, but I think the point was to show that you can always construct a predicate, P over a and b, such that P(a, b) is finitely defined (such as "a > 20 and b > 20"), but {(a, b) | P(a, b) is true} is infinite and monochromatic.

Instead of having some cases of colorings where your only option is to construct things of the form "(a = 5 and b = 17) or (a = 3 and b = 47) or ..." where you just list out every pair that matches (in an infinite subset).

> More surprisingly perhaps, if you colour the infinite subsets of the natural numbers red or blue, then there exist colourings for which there is no monochromatic subset.

Could you elaborate on this?

Yes, a little, although it's on the fringes of my knowledge on the subject. Suppose, instead of colouring all the pairs of natural numbers like {2,3} or {100, 1056}, you colour all the infinite sets of natural numbers like the set of all odd numbers {1, 3, 5, ...} or the set of powers of two {2, 4, 8, ... }. Every possible infinite set must be coloured either red or blue.

Now, if the Ramsey theorem were to extend to this scenario, then for every possible red/blue colouring there would be some (necessarily infinite) subset A of natural numbers which is "monochromatic", i.e. every infinite subset of A receives the same colour. However, this isn't the case. It's possible to show there exists a very clever colouring which excludes the possibility of having an infinite monochromatic subset. I've only seen proofs of this which use the axiom of choice and are not constructive (although I don't know if this is always necessarily so), but the top reply to this question is one of the nicer proofs: http://math.stackexchange.com/questions/282827/does-a-red-bl...

This is surprising partly because if you take an arbitrarily large number n and colour all sets of natural numbers with cardinality n, then you will still get an infinite monochromatic subset.

Edit: the second response in the above link argues that the Axiom of Choice is a necessary assumption in the proof. This is probably one of those unsatisfying results which says "we know this thing exists, but we also know that we'll never be able to construct or define it explicitly".

Reply on news.ycombinator.com