4 ms·

The Four Color Theorem And Algorithm

15 points by cjg 18y ago

RiderOfGiraffes 18y ago
This has been around for at least 10 years - the bottom of the web page says "13 November 1995." As a PhD in graph theory I'm curious to know: * why do you think this is interesting? * what other 10 or 20 year old results might you be interested in? I have lots ...
- JoelSutherland 18y ago
  It is interesting because it is easy to understand the problem quickly -- we've all seen maps. Additionally, for graph theory, the solution is pretty accessible. I took just an introductory course in graph theory so I only got to see this famous problem and a few others. I would think that this crowd would find a list of other famous problems from your field quite interesting.
  - RiderOfGiraffes 18y ago
    the solution is pretty accessible. I don't think that's true. I think you'll find the proof that discharging gives you what you want is pretty impenetrable. And this is a review of a survey paper that doesn't actually give the details. I guess in this case I know too much about the topic to be able to assess whether it will be interesting to a generic hacker. I think it's pretty content-free. That's probably also the difference between me and a good science writer. Anything I read about something I know seems to be complete content-free fluff. I've tried, but I don't think I'll ever be able to write anything for general consumption. However, here are a couple of results and/or odd questions: * Given a Turing Machine one can construct a graph such that 3-coloring the graph is equivalent to running the Turing machine. >> Since 3-coloring doesn't have a "direction", that means you can effectively run the TM backwards. >>> That is a direct proof that 3-coloring is NP-complete. * The set of reals is bigger than the set of integers * One cannot decide from the axioms of set theory whether there is a set of reals that is bigger than the set of integers, but smaller than the set of reals. * pi is very closely approximated by 355/113 * Define the sequence k(1)=0, k(2)=2, k(3)=3, k(n)=k(n-2)+k(n-3), and for n>1 ask: Does n divide k(n)? The answer is always "Yes" if n is prime, and almost always "No" if n is composite. Challenge: find the first 5 cases where it gives the "wrong" answer. Finally: * What do you get if you photocopy a mirror?
    - emmett 18y ago
      I found this post interesting. I'd subscribe to your blog if the posts were about things like this.
      - RiderOfGiraffes 18y ago
        Oh. Gosh. <fx: blush> I might have to think about getting a blog, then ...
    - jules 18y ago
      I don't understand your first bullet point about turing machines. Can you elaborate? > * What do you get if you photocopy a mirror? Black?
      - RiderOfGiraffes 18y ago
        >> What do you get if you photocopy a mirror? > Black? Are you sure? Why? Can you prove it from first principles? It's an interesting challenge - prove that a well-designed photocopier must give a particular result. > I don't understand your first bullet point about turing machines. Can you elaborate? This would be a lot easier if I took considerable time and drew pictures to illustrate. Without, this will be a bit of a slog. I hope it's helpful ... So. It's possible to construct graphs such that a valid three coloring results in behavior equivalent to actions of a logic gate. For example, suppose your colors are called "0", "1" and "#". Take a triangle and color one vertex "#". Label the other vertices "in" and "out". Now you have a "NOT" gate. You can feed the output of one gate into the input of another by identifying the vertices. This allows you to build combinatorial circuits. Now take some instance of any NP problem. (technical terms. A "problem" is a collection of "instances".) A simple example to understand is factoring. Clearly any alleged solution can be checked in polynomial time simply by multiplying the alleged factors and seeing if you get the right answer. Hence the problem is in NP. So given an instance N - a number to factor - construct a TM to multiply two numbers and check if the answer is N. If it is, output "yes". If not, output "no". (There are details about what "output" means for a TM. These can be done.) Now construct the combinatorial circuit that mimics running the TM. Note, it's polynomial in in size because the TM is poynomial in size and runs in polynomial time. (There are details about how that can be done.) Now we have a graph which, if you color the input vertices with a factorization of N, results in the "Yes" vertex getting the color "1". Force the color of the "yes" vertex to be "1" and find a coloring. (How to force a given vertex is a simple technical trick.) If you succeed, then the "input" vertices must hold a valid factorization of N. Thus we have constructed a graph to emulate the TM that multiplies, and run it backwards to make it a factoring machine. This proves that 3-coloring is "harder" than factoring. However, the construction goes through for any NP problem, and hence 3-coloring is NP-hard. Given that 3-coloring is also itself in NP, that shows that 3-coloring is NP-complete. Does that answer your question?

15 points by cjg 18y ago

This has been around for at least 10 years - the bottom of the web page says "13 November 1995." As a PhD in graph theory I'm curious to know: * why do you think this is interesting? * what other 10 or 20 year old results might you be interested in? I have lots ...

JoelSutherland 18y ago
It is interesting because it is easy to understand the problem quickly -- we've all seen maps. Additionally, for graph theory, the solution is pretty accessible. I took just an introductory course in graph theory so I only got to see this famous problem and a few others. I would think that this crowd would find a list of other famous problems from your field quite interesting.
- RiderOfGiraffes 18y ago
  the solution is pretty accessible. I don't think that's true. I think you'll find the proof that discharging gives you what you want is pretty impenetrable. And this is a review of a survey paper that doesn't actually give the details. I guess in this case I know too much about the topic to be able to assess whether it will be interesting to a generic hacker. I think it's pretty content-free. That's probably also the difference between me and a good science writer. Anything I read about something I know seems to be complete content-free fluff. I've tried, but I don't think I'll ever be able to write anything for general consumption. However, here are a couple of results and/or odd questions: * Given a Turing Machine one can construct a graph such that 3-coloring the graph is equivalent to running the Turing machine. >> Since 3-coloring doesn't have a "direction", that means you can effectively run the TM backwards. >>> That is a direct proof that 3-coloring is NP-complete. * The set of reals is bigger than the set of integers * One cannot decide from the axioms of set theory whether there is a set of reals that is bigger than the set of integers, but smaller than the set of reals. * pi is very closely approximated by 355/113 * Define the sequence k(1)=0, k(2)=2, k(3)=3, k(n)=k(n-2)+k(n-3), and for n>1 ask: Does n divide k(n)? The answer is always "Yes" if n is prime, and almost always "No" if n is composite. Challenge: find the first 5 cases where it gives the "wrong" answer. Finally: * What do you get if you photocopy a mirror?
  - emmett 18y ago
    I found this post interesting. I'd subscribe to your blog if the posts were about things like this.
    - RiderOfGiraffes 18y ago
      Oh. Gosh. <fx: blush> I might have to think about getting a blog, then ...
  - jules 18y ago
    I don't understand your first bullet point about turing machines. Can you elaborate? > * What do you get if you photocopy a mirror? Black?
    - RiderOfGiraffes 18y ago
      >> What do you get if you photocopy a mirror? > Black? Are you sure? Why? Can you prove it from first principles? It's an interesting challenge - prove that a well-designed photocopier must give a particular result. > I don't understand your first bullet point about turing machines. Can you elaborate? This would be a lot easier if I took considerable time and drew pictures to illustrate. Without, this will be a bit of a slog. I hope it's helpful ... So. It's possible to construct graphs such that a valid three coloring results in behavior equivalent to actions of a logic gate. For example, suppose your colors are called "0", "1" and "#". Take a triangle and color one vertex "#". Label the other vertices "in" and "out". Now you have a "NOT" gate. You can feed the output of one gate into the input of another by identifying the vertices. This allows you to build combinatorial circuits. Now take some instance of any NP problem. (technical terms. A "problem" is a collection of "instances".) A simple example to understand is factoring. Clearly any alleged solution can be checked in polynomial time simply by multiplying the alleged factors and seeing if you get the right answer. Hence the problem is in NP. So given an instance N - a number to factor - construct a TM to multiply two numbers and check if the answer is N. If it is, output "yes". If not, output "no". (There are details about what "output" means for a TM. These can be done.) Now construct the combinatorial circuit that mimics running the TM. Note, it's polynomial in in size because the TM is poynomial in size and runs in polynomial time. (There are details about how that can be done.) Now we have a graph which, if you color the input vertices with a factorization of N, results in the "Yes" vertex getting the color "1". Force the color of the "yes" vertex to be "1" and find a coloring. (How to force a given vertex is a simple technical trick.) If you succeed, then the "input" vertices must hold a valid factorization of N. Thus we have constructed a graph to emulate the TM that multiplies, and run it backwards to make it a factoring machine. This proves that 3-coloring is "harder" than factoring. However, the construction goes through for any NP problem, and hence 3-coloring is NP-hard. Given that 3-coloring is also itself in NP, that shows that 3-coloring is NP-complete. Does that answer your question?