Mathematicians Solve Long-Standing Coloring Problem
quantamagazine.org
Mathematicians Solve Long-Standing Coloring Problem
1–10 of 10 posts
Re: Mathematicians Solve Long-Standing Coloring Problem
#2Is this somehow related to the Four color problem? https://en.wikipedia.org/wiki/Four_color_theorem
Re: Mathematicians Solve Long-Standing Coloring Problem
#3Is this somehow related to the Four color problem? https://en.wikipedia.org/wiki/Four_color_theorem
Not in any straightforward way I can see. Some obvious differences:
- This result has effectively only two colours: "coloured" and "not coloured".
- This relates to an infinite continuous plane of points rather than a finite, discrete set.
- This has a notion of distance, whereas the four-colour theorem is more about connectivity.
That said, the idea of using a computer to aid a proof did also occur in the original proof of the four colour theorem.
Re: Mathematicians Solve Long-Standing Coloring Problem
#4Is this somehow related to the Four color problem? https://en.wikipedia.org/wiki/Four_color_theorem
Not really. That is concerned with much less rigid planar structures. What this is directly related to is the famous unsolved https://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_proble... , the number of colors needed to color the plane if we do not allow unit intervals to have identically colored endpoints. The above Wikipedia link has a nice visual proof that the minimal number of colors is between 4 and 7 (https://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_proble...), and Aubrey de Grey's famous 2018 construction shows that it is larger than 4.
Re: Mathematicians Solve Long-Standing Coloring Problem
#5(Submitter here, but also one of the authors of the presented work.)
The Quanta article rushed through some aspects of our work, so I'll try to use this opportunity to elaborate. This has a very small target audience: those who have skimmed the original post, and would like to go a bit deeper. AMA!
Alice gives us a unit distance avoiding set. We want to prove that its density is less than 1/4. Independently, Bob gives us an n element point set on the plane. We use it to translate Alice's set into n translated versions, take all 2^n possible n-wise intersections between these translations, and write up a tricky and huge linear program for the densities of these intersections. Solving that LP gives us an upper bound for the density of Alice's set.
Bob's finite set works for any set coming from Alice. So we have reduced Erdős's problem to finding a finite set with the property that its LP objective is less than 1/4. That is the search problem that we solve by starting from the 7 element Moser spindle, and incrementally adding points to it, guided by a modified beam search. The LP size is exponential in the number of points, but before exhausting memory and/or CPU budget, the search has come back with a 23 element set that is a witness to the fact that the Erdős's conjecture is true. (It is the weird graph in supplementary material https://bit.ly/unit-distances )
Re: Mathematicians Solve Long-Standing Coloring Problem
#6Is this somehow related to the Four color problem? https://en.wikipedia.org/wiki/Four_color_theorem
Not in any straightforward way I can see. Some obvious differences: - This result has effectively only two colours: "coloured" and "not coloured". - This relates to an infinite continuous plane of points rather than a finite, discrete set. - This has a notion of distance, whereas the four-colour theorem is more about connectivity. That said, the idea of using a computer to aid a proof did also occur in the original p…
[deleted]
Re: Mathematicians Solve Long-Standing Coloring Problem
#7Is this somehow related to the Four color problem? https://en.wikipedia.org/wiki/Four_color_theorem
Not really. That is concerned with much less rigid planar structures. What this is directly related to is the famous unsolved https://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_proble... , the number of colors needed to color the plane if we do not allow unit intervals to have identically colored endpoints. The above Wikipedia link has a nice visual proof that the minimal number of colors is between 4 and 7 ( http…
Sincere question, the article as you do mentions the connection with the Hadwinger-Nelson problem too but I still don't see quite well how they are related, how could one pose them using mathematical terminology to better be able to contrast both problems and see their similarities and differences?
Re: Mathematicians Solve Long-Standing Coloring Problem
#8Earlier quoted context omitted.
Not really. That is concerned with much less rigid planar structures. What this is directly related to is the famous unsolved https://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_proble... , the number of colors needed to color the plane if we do not allow unit intervals to have identically colored endpoints. The above Wikipedia link has a nice visual proof that the minimal number of colors is between 4 and 7 ( http…
Sincere question, the article as you do mentions the connection with the Hadwinger-Nelson problem too but I still don't see quite well how they are related, how could one pose them using mathematical terminology to better be able to contrast both problems and see their similarities and differences?
Sorry, I've just spotted your question 3 days late. The Moser-Erdős question is about how large the density of a unit distance avoiding set can be. The Hadwiger-Nelson question is about how many unit distance avoiding sets are necessary to cover the whole plane.
As David Eppstein phrased it (https://mathstodon.xyz/@11011110/110810118775049296), ours is the independent set version of Hadwiger-Nelson. That is, the relationship between the two questions is analogous to the relationship between graph chromatic number and graph independence number.
If you define independence ratio as the ratio of the independence number and the vertex number, then this is a bit more than just an analogy. If you build a huge grid of very tiny squares, and connect two tiny squares with an edge if there's an unit distance between them, then in the limit, the independence ratio of this graph is the density that we've looked at, and the chromatic number of this graph is the measurable chromatic number of the plane.
Re: Mathematicians Solve Long-Standing Coloring Problem
#9Earlier quoted context omitted.
Sincere question, the article as you do mentions the connection with the Hadwinger-Nelson problem too but I still don't see quite well how they are related, how could one pose them using mathematical terminology to better be able to contrast both problems and see their similarities and differences?
Sorry, I've just spotted your question 3 days late. The Moser-Erdős question is about how large the density of a unit distance avoiding set can be. The Hadwiger-Nelson question is about how many unit distance avoiding sets are necessary to cover the whole plane. As David Eppstein phrased it ( https://mathstodon.xyz/@11011110/110810118775049296 ), ours is the independent set version of Hadwiger-Nelson. That is, the re…
Don't worry I spotted your answer 4 days late. Had to read the intro to the paper to understand what you were pointing to me (in fact maybe I should have tried before asking my first question) only section 1 the rest is beyond me, if I understood right we have that,
m_1(R^2)What I'm not sure of is how X_f(R^2) relates to X(R^2) that is if we were to find that the chromatic number of the plane is X(R^2)=6 then what can we say about fractional chromatic number X_f(R^2)?
Hope you see this post and if not it was still super useful, thanks a lot!
Re: Mathematicians Solve Long-Standing Coloring Problem
#10Earlier quoted context omitted.
Sorry, I've just spotted your question 3 days late. The Moser-Erdős question is about how large the density of a unit distance avoiding set can be. The Hadwiger-Nelson question is about how many unit distance avoiding sets are necessary to cover the whole plane. As David Eppstein phrased it ( https://mathstodon.xyz/@11011110/110810118775049296 ), ours is the independent set version of Hadwiger-Nelson. That is, the re…
Don't worry I spotted your answer 4 days late. Had to read the intro to the paper to understand what you were pointing to me (in fact maybe I should have tried before asking my first question) only section 1 the rest is beyond me, if I understood right we have that, m_1(R^2) What I'm not sure of is how X_f(R^2) relates to X(R^2) that is if we were to find that the chromatic number of the plane is X(R^2)=6 then what c…
The fractional chromatic number of the plane is by definition less than or equal to the regular chromatic number of the plane, but already we know for sure that they are not equal. We know that 5 [1] https://www.sfu.ca/~vjungic/RamseyNotes/Fractional.html