tag:blogger.com,1999:blog-3722233.post3692047415217655802..comments2023-03-25T10:00:22.914-05:00Comments on Computational Complexity: Equations and Colorings: Rado's theoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-76407042899194805152007-11-05T23:35:00.000-06:002007-11-05T23:35:00.000-06:00If all color classes are measurable, then one of t...If all color classes are measurable, then one of them must have positive measure, and so there has to be an interval within which that color class has density, say, 99%. Say that, after scaling, the interval is [0,1], then pick at random x in [0,1/4], w in [1/4,1/2] and epsilon in [0,1/2], and set z=x+epsilon and y = w+epsilon. Then by the union bound there is at least a 88% probability (or something like that) that all four points have the same color, and by construction x-z=w-y.<BR/><BR/>So if the answer is that a coloring exists, its definition must use the axiom of choice, because otherwise you can't construct non-measurable sets. (Under the proper assumptions, like ZF plus some cardinal assumption is consistent.)Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4217924528575537362007-11-04T20:49:00.000-06:002007-11-04T20:49:00.000-06:00either yes or no would be a boring answer...I'm go...either yes or no would be a boring answer...<BR/><BR/>I'm gonna go with it's equivalent to the negation of the Axiom of Choice. Or something.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33281321207991235752007-11-04T07:43:00.000-06:002007-11-04T07:43:00.000-06:00In your first equation you write 2x+3x-6z = 0. One...In your first equation you write 2x+3x-6z = 0. One of the x's is probably a y, right?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52357957312786991152007-11-04T05:57:00.000-06:002007-11-04T05:57:00.000-06:00I believe it's true from measure theory arguments(...I believe it's true from measure theory arguments(you need to find 2 pairs which are same distance)SurDinhttps://www.blogger.com/profile/00452466544052631040noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16796181163742156362007-11-03T19:58:00.000-05:002007-11-03T19:58:00.000-05:00What the hell? Aren't you guys sick of coloring al...What the hell? Aren't you guys sick of coloring already given that everyone has been talking about coloring the graphs this way or that way, that now you have moved to coloring those innocent natural and real numbers? STOP DOING THAT!! All things colored not necessarily look good. At least leave N and R uncolored. Coloring, coloring, coloring, HUH!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66578418086110458762007-11-03T18:52:00.000-05:002007-11-03T18:52:00.000-05:00I suppose you can call it a stupid question if you...I suppose you can call it a stupid question if you are one of those people who would like to get rid of the axiom of choice, for example.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81444944041672372532007-11-03T16:50:00.000-05:002007-11-03T16:50:00.000-05:00You can't even color any interval, no matter how s...<I>You can't even color any interval, no matter how small, with the same color!</I><BR/><BR/>But the same thing would be true if you considered using only 2 colors for R.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78831665487268386852007-11-03T16:32:00.000-05:002007-11-03T16:32:00.000-05:00>You can't even color any interval, no matter how ...>You can't even color any interval, no matter how small, with the same color!<BR/><BR/>Well, what would prevent you from doing so.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37055802206900114592007-11-03T11:57:00.000-05:002007-11-03T11:57:00.000-05:00This would be a "stupid" (i.e. trivial) problem if...This would be a "stupid" (i.e. trivial) problem if you had a monochromatic interval of positive length. However, a finite number of colors won't guarantee that either.<BR/><BR/>I would actually guess that it's false, but I have to think about it a bit more.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22091618698580741462007-11-03T08:53:00.000-05:002007-11-03T08:53:00.000-05:00Hummm... I didn't realize the number of colors did...Hummm... I didn't realize the number of colors didn't have to be finite. I'm changing my vote to "a stupid question", which just means "a question I don't really care about".<BR/><BR/>The reason I don't care about it is that the problem is based on this extremely discontinuous use of the reals, where you can do things like assign each rational number a different color. You can't even color any interval, no matter how small, with the same color!Guilhermehttps://www.blogger.com/profile/16356657960297015642noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2932649846652682392007-11-03T07:20:00.000-05:002007-11-03T07:20:00.000-05:00Why did those who thought it was a stupid question...Why did those who thought it was a stupid question think it was a stupid question?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41675892735846702552007-11-03T04:51:00.000-05:002007-11-03T04:51:00.000-05:00I should actually revise my comment, you should be...I should actually revise my comment, you should be looking for one partition containing the 4 integers (I read "same color" as "different colors" in the second part of my post).<BR/><BR/>But I still think it's true for some reason!SampaioXhttps://www.blogger.com/profile/10040530208721411062noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26159516405741385702007-11-03T04:47:00.000-05:002007-11-03T04:47:00.000-05:00guilherme: it couldn't be true for N because you c...guilherme: it couldn't be true for N because you could color each integer a distinct color.<BR/><BR/>But I agree that my hunch says it's true for R. I reformulate the question as follows: if you partition the reals into countably many subsets, can you always find four of them P1,...,P4 such that there are x1,...,x4 in the P's such that any two of them add up to the other two.<BR/><BR/>My intuition screams yes. Mind you, my intuition about the reals has been wrong before.SampaioXhttps://www.blogger.com/profile/10040530208721411062noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12711188894173896282007-11-02T19:23:00.000-05:002007-11-02T19:23:00.000-05:00enjoying your notes so far, Bill...small typo note...enjoying your notes so far, Bill...<BR/><BR/>small typo note: page two, point 3 on your list, I see a j where there should be a k.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55264193019962394332007-11-02T18:35:00.000-05:002007-11-02T18:35:00.000-05:00I think it's true. I'd still guess true if you rep...I think it's true. I'd still guess true if you replaced R with N, and I believe the constants for the first problem were carefully choosen to make the answer false.Guilhermehttps://www.blogger.com/profile/16356657960297015642noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91862997164264391752007-11-02T16:24:00.000-05:002007-11-02T16:24:00.000-05:00Thanks for the correction,I have made it.Thanks for the correction,<BR/>I have made it.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69681210035566350822007-11-02T14:37:00.000-05:002007-11-02T14:37:00.000-05:00Did you mean x+y=z+w?Did you mean x+y=z+w?Anonymousnoreply@blogger.com