Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Equations and Colorings: Rado's theorem

Expand Messages
  • GASARCH
    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
    Message 1 of 1 , Nov 2, 2007
    View Source
    • 0 Attachment
      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 = 0
      It 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 = 0
      The 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
      1. 5 thought it was TRUE
      2. 4 thought it was FALSE
      3. 5 thought it was a STUPID QUESTION.



      --
      Posted By GASARCH to Computational Complexity at 11/02/2007 02:26:00 PM
    Your message has been successfully submitted and would be delivered to recipients shortly.