Subscribe to Macosxnerd101's Blog
21 Comments
This semester, I am taking a class called Applied Combinatorics, which has a large Graph Theory component. Today, my professor was introducing planar graphs. We got sidetracked on the Four Color Theorem, which states that a planar graph requires no more than four distinct colors so that no adjacent faces have the same color. I have been working on a proof for this theorem on and off today, and I'm going into his office hours on Wednesday to talk about it more. College has really gotten me hooked on proofs, since I took Discrete Math (proofs for CS students at Tech) last semester. On top of that, my proof writing has really improved. And of course, hooray for Graph Theory!
Categories: Uncategorized
Share This Entry:
21 Comments On This Entry
nick2price
03 September 2012 - 05:27 PM
You need to start taking some more difficult classes, I mean, Applied Combinatorics... 
modi123_1
04 September 2012 - 07:12 AM
Nice.. I remember my Combinatorics and Number Theory class with fondness. Graph Theory was fun as well, but the Language Theory and Automata was a load of love/hate. Ha.
atraub
04 September 2012 - 07:25 AM
ahh the 4 color theorem, I love the 4 color theorem. Good luck creating a proof that takes less than a hundred pages
You know, I always felt there was a correlation between the 4 color theorem and the fact that if you create a graph that has 4 vertices, you can create a complete graph with no overlapping edges, but with 5 vertices this becomes impossible. Similarly, you can create 2D maps that require 4 colors to be displayed with no overlapping colors, but to trying to create one that requires 5 is impossible. Of course, I'm sure I'm not the first guy to say this lol.
You know, I always felt there was a correlation between the 4 color theorem and the fact that if you create a graph that has 4 vertices, you can create a complete graph with no overlapping edges, but with 5 vertices this becomes impossible. Similarly, you can create 2D maps that require 4 colors to be displayed with no overlapping colors, but to trying to create one that requires 5 is impossible. Of course, I'm sure I'm not the first guy to say this lol.
atraub
04 September 2012 - 07:26 AM
awww... I can't edit the typos in my comment 
Array ( [0] => Array ( [0] => 712 [1] => There was an error with checking that category. 4921:4921:0 Function: category::checkCategory ) )
macosxnerd101
04 September 2012 - 07:36 AM
@atraub: My professor has basically said that there isn't a good proof for this theorem. It has been bugging me so I decided to tackle it. Honestly, I'm probably missing something. My proof is a little over a page. Tackling this proof has been a good learning experience, and I'm interested to see what I get out of having it destroyed.
@modi123_1: I get to take Modern Algebra next semester, which will set me up well for Number Theory. I think Formal Languages will have to wait for another couple semesters.
@modi123_1: I get to take Modern Algebra next semester, which will set me up well for Number Theory. I think Formal Languages will have to wait for another couple semesters.
modi123_1
04 September 2012 - 09:37 AM
I do believe I spent more time in the library studying my language theory than all my other classes for the tenure of college combined. It was spooky - the farther into I got the more panicked I was because it wasn't making sense but the better my grades became. A freaking mystery.
macosxnerd101
04 September 2012 - 09:48 AM
@atraub: Actually, the four color theorem deals with faces, not vertices. It is quite possible to create a planar graph with five vertices. Complete graphs stop being planar starting at K5.
macosxnerd101
04 September 2012 - 09:49 AM
modi123_1: That's rough. I won't take Formal Languages on an 18 hour semester then if I opt to take it. I need algorithm analysis, and AI and Theory of Computation look interesting as well!
nuclearfroggy
04 September 2012 - 01:18 PM
Graph theory seems really interesting. "An Introduction to Graph Theory" by Trudeau gives a really good overview, sadly I don't think I'll get much contact with it in my electronic engineering course. I like how it feels like starting maths from scratch, it's so different from any other maths stuff you encounter at high school.
From what I read I thought the 4 colour theorem was only proven by a computer because of the gazillion combinations you have to go through.
From what I read I thought the 4 colour theorem was only proven by a computer because of the gazillion combinations you have to go through.
atraub
04 September 2012 - 04:21 PM
I'm extremely familiar with the 4 color theorem, I actually obsessed over it for quite a while, and it's among my favorite math puzzles (it's a nice one to show that math isn't all that stuffy). If it only dealt with vertices, then you could disprove it simply by making a map that looks like a pizza.
However, let's say that you took your map, and then turned it into a far simpler graph. Make every vertex on your graph represent a region on your map. Next, connect the vertices on your graph; do this by having each edge represent a shared face on the map. For any 2D map, a corresponding graph exists with no overlapping edges. I believe that there are deeper things that can be derived from this, but sadly, I don't have the math background to take it any further than that.
However, let's say that you took your map, and then turned it into a far simpler graph. Make every vertex on your graph represent a region on your map. Next, connect the vertices on your graph; do this by having each edge represent a shared face on the map. For any 2D map, a corresponding graph exists with no overlapping edges. I believe that there are deeper things that can be derived from this, but sadly, I don't have the math background to take it any further than that.
atraub
04 September 2012 - 04:36 PM
This image should better illustrate the map to graph conversion
For every graph with no overlapping edges, a corresponding 2D map can be generated that can be displayed with only four colors. For every 2D map that can be generated, a corresponding graph can be created with no overlapping edges. If you create a graph that can not be displayed with no overlapping edges (for example a complete graph with 5 vertices) a corresponding 2D map can NOT be generated. Does this better explain my little conjecture?
For every graph with no overlapping edges, a corresponding 2D map can be generated that can be displayed with only four colors. For every 2D map that can be generated, a corresponding graph can be created with no overlapping edges. If you create a graph that can not be displayed with no overlapping edges (for example a complete graph with 5 vertices) a corresponding 2D map can NOT be generated. Does this better explain my little conjecture?
atraub
04 September 2012 - 04:38 PM
Damn broken edit button!!
For every graph with no overlapping edges For every graph that can be displayed with no overlapping edges.
atraub
04 September 2012 - 05:49 PM
I re-read your comments, sure wish I had noticed the word "planar" before I wrote mine :-P
macosxnerd101
04 September 2012 - 06:42 PM
@atraub: You're talking about the dual graphs. I remember that from Graph Theory in high school Discrete a couple years back. Duals only exist for planar graphs. I met with my professor today. The big hole he tore in my proof was that it relied on adjacent faces. Instead, I just need to show that the four faces are each colored distinctly. My proof also built up the graph rather than starting with a graph and analyzing properties. I'm reworking it now and am going to turn it into him tomorrow in class.
atraub
04 September 2012 - 07:51 PM
Well wait, it IS a dual graph of sorts, but it doesn't seem to be quite the same as what wikipedia shows (I think). My dual graph accounts for faces that share edges rather than vertices. I believe that a pizza-like map would create a connected dual graph, where my modified dual graph would look more like a circle where every vertex only shares an edge with the two vertices representing adjacent faces.
macosxnerd101
04 September 2012 - 09:10 PM
Faces that share edges cannot have the same color, while faces that only share vertices can in fact have the same color.
atraub
05 September 2012 - 06:18 AM
that's correct, I never said anything to the contrary... did you misread something?
My Blog Links
Recent Entries
Recent Comments
Search My Blog
5 user(s) viewing
5 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)
| 