[Computational Complexity] Equations and Colorings: Rado's theorem
- Is the following TRUE or FALSE?
For every 17-coloring of N (the naturals- not including 0) there exists x, y, z such that x,y,z are distinct x,y,z that are same color such that 2x+3x-6z = 0It turns out that this is FALSE.We'll call a set b1,...,bn REGULAR if
for every c, for every c-coloring of N, there exists x1,....,xn such thatx1,....,xn are all the same color, andb1x1 + ... + bnxn = 0The following is known as (abridged) Rado's Theorem. Rado proved it in 1933.
(b1,...,bn) is regular iff some nonempty subset of the bi's sum to 0.For an exposition of the proof see Ramsey Theory by Graham, Rothchild,and Spencer or see my writeup
NOW- here is a question to which the answer is known, and I'll tell you the answer in my next post.
TRUE OR FALSE:
For every coloring of R (the reals) with a countable number of colors there exists distinct x,y,z,wx,y,z,w same colorx+y=x+w.When I asked this in seminar I got
- 5 thought it was TRUE
- 4 thought it was FALSE
- 5 thought it was a STUPID QUESTION.
Posted By GASARCH to Computational Complexity at 11/02/2007 02:26:00 PM