What's the importance of this open question?

232 Views Asked by At

One of the open problems in graph theory is the chromatic number of the plane

It asks what is the minimum number of colors needed to color every point in a plane such that two points of unit distance apart are not the same color.

What is the importance of this open problem? So far the number is between 4 and 7, but if we do find a better bound or even the answer, what implications will it have?

1

There are 1 best solutions below

2
On BEST ANSWER

The answer is that we don't know yet.

As Arthur said, the Hadwiger-Nelson problem doesn't (as far as we know) hold a lot of significance itself. But a few things are known about it which make it more interesting than just a simple curiosity:

  1. If the sets are required to be Lebesgue-measurable, at least 5 colors are needed, while if they are required to be bounded by Jordan curves, at least 6 are required. This means that, if the answer is 4 or 5 (especially if it's 4), a coloring would be "strange" in that the regions can't be "very nice". Such a coloring could be important towards solving other problems (see Arthur's example of Fermat's Last Theorem and the techniques used to prove it).
  2. Related to (1.), a proof that it is not 4-colorable would likely involve some sort of finite subgraph of the unit distance graph that is not 4-colorable (in fact, the De-Bruijn-Erdos Theorem implies that such a subgraph must exist if the infinite graph is not 4-colorable. Such a graph could be useful in other areas of graph theory.
  3. Enigmatically, this problem is rather interesting, in that the known bounds (4 and 7) can be achieved through very elementary methods. I believe showing that the chromatic number of the plane is at least 4 is a common exercise in pre-Olympiad combinatorics. The fact that very little is known about the structure of this problem makes it a more interesting "enigma".

Also, and I know this is not directly an answer to your question, but I feel it should be stated: Not all problems have other known applications until much later. Before the theory of modular forms, Fermat's Last Theorem would likely have been thought of as just a mathematical curiosity, but it ended being related to a much deeper mathematical problem (the modularity theorem). Just because we don't know now what a solution to the Hadwiger-Nelson problem might mean for graph theory or other areas of math doesn't mean that it won't mean anything.