|
| Author | Message / Information |
| cramwit Quote | Reply | | 4 color map theorem posted on: 3/6/2007 11:03:34 AM Once one understands that any map is essentially a graph structure the proof is trivial. Each cell is a vertex & each adjacency between cells is an edge/connection between two cells. Mutual adjacency is what requires color differentiation. Since it is a graph structure no more than 4 points call be mutually adjacent. Therefore there is [will never be] no need for more than 4 colors. end of proof. Conceptualizing the map as its graph equivalent: 1. Imagine plastically shrinking an individual cell down to a point. You can see radially around it points form from each of the neighboring cells. Imagine releasing the map back but for this cell it stays a point and only a string/line/edge connection attaches it to each of the original neighbor cells. The body of the cell has been removed, but not its logic. Do that for each cell & you get the graph equivalent of the original map. 2. Each cell is topologically a polygon. each distinct adjacency is a [curvy] segment of that polygon. Each segment creates a connection/adjacency between cells. Take the original map drawn in black on a white surface. Use a different color [blue] and dab a single interior point in each cell that will represent it. Then draw one edge that [approximately] intersects the cell wall segment perpendicularly between the two cell center points that it is an adjacency for. You will end up with the skeletal logic of the map in blue with the cell outlines in black. Mathematically/logically they are equivalent. Additionally i believe i can prove a similar case for a map on a sphere or topological equivalent. |
|
cramwit
Quote | Reply | |
4 color map theorem
replied on: 3/10/2007 12:35:10 PM Mechanically precise way of constructing the underlying graph of a map. Choose an arbitrary point in the interior of the cell to be the 'cell' vertex. mark the midpoint of each [curvy] adjacency segment. Draw non-overlapping lines from the vertex to each midpoint, creating half-edges, with the other half in each corresponding adjacent cell. Do that for every cell & you have the graph structure. Adjacencies can not overlap/cross without going into the 3rd dimension so edges in the graph can not overlap. It seems pretty apparent to me. Obviously others do not seem to be seeing it this way. |
|
cramwit
Quote | Reply | |
4 color map theorem
replied on: 3/13/2007 1:36:02 AM Perhaps there is a question about why 5 points can not be mutually adjacent in a plane. Firstly we have to accept/understand the axiom that any cycle in a plane bifurcates the remaining points of the plane [2D manifold?]. Which i suspect works as a/the definition of a plane: A plane is a space where any cycle of/within the space bifurcates it. Why five points can not be both co-planar & mutually adjacent/connectible: starting with a triangle a-b-c it bifurcates the non-triangle points into abc point (interior, arbitrary) & NOT abc points (exterior,arbitrary) we choose a point d from the NOT abc points. we construct edges a-d & d-b creating the triangle d-a-b again arbitrarily we define dab (interior) points as the ones NOT including c we know the remainder of the plane is the intersection of NOT abc & NOT dab we know anything constructed of these points can only be peripherally connected to a-b-c, d-a-b, a, b, c, d we construct edge d-c bifurcating this remainder of the plane creating two additional triangles which consume all the remaining points of the plane since b is not part of the construct of triangle d-a-c it is therefore exterior to it since a is not a part of the construct of triangle d-b-c it is therefore exterior to it The entire plane is consumed by 4 triangles each of which exclude their non-included point. since there is no portion of the plane common or adjacent [& planar connectible] to all 4 points there can be no point e that can be mutually adjacent to all of them. |
|
Pythagoras
Quote | Reply | This message was updated on 3/13/2007 8:06:24 PM by Pythagoras |
4 color map theorem
replied on: 3/13/2007 8:05:39 PM I heard of this 4 colour problem/theorem mentioned before in my classes, but i didn't really pay attention. What is the 4 color theorem? What is the 4 colour problem? Are they the same thing. I'll put some chemical energy into trying to under this thread soon. Pythagoras |
|
cramwit
Quote | Reply | |
4 color map theorem
replied on: 3/14/2007 8:21:22 AM Yes they both refer to the same classic problem/question, If you want no two adjacent regions of a map to have the same color are 5 colors ever necessary? There has never been a map created that needs more than 4 colors, but no one seems to have ever come up with a proof. touching region/cell points doesn't count as adjacent, they must share some length of linear edge. |
|
Pythagoras
Quote | Reply | This message was updated on 3/14/2007 9:01:09 PM by Pythagoras |
4 color map theorem
replied on: 3/14/2007 8:38:06 PM Yeah. I checked out the problem a bit on the net today...i've heard it mentioned at school before.... Yeah, the 4 color "problem" and the 4 color "theorem" means the same thing; i read this. Probably better to call it a problem though i think. You say there's no proof of it? I thought i read on a site today that there is a proof of it. I think i read something about there was a "computer proof" which had way way too many 'variables' and it being way too technical...so some of The Big Boys didn't accept it as a 'real' proof...or something like that... Then two guys discovered a better but still very complex proof or something like that... Maybe there's no real nice, sturdy, simple, short proof... Pythagoras |
|
Pythagoras
Quote | Reply | This message was updated on 3/15/2007 11:40:20 AM by Pythagoras |
4 color map theorem
replied on: 3/14/2007 8:53:57 PM "Mechanically precise way of constructing the underlying graph..." So let's say we had 4 small squares all the same size...and we bring them together to get a big square in a plane. So we have 4 cells...hence 4 vertices...this mechanical method will give us a graph which is a rectangle... But! the diagonals of this rectangular graph is not included? If these diagonals are not included then i think i more-or-less under what's going on; for now.  Pythagoras |
|
cramwit
Quote | Reply | |
4 color map theorem
replied on: 3/15/2007 3:22:54 PM apologies, yes there is a proposed computer proof. Yes map regions, as your square corners/points are not considered adjacent. They must have some length of border greater than a point making contact. Thanks for illustrating the basic idea i am proposing. each cell is topologically a polygon. each segment of that polygon is adjacent to & therefore would have an edge that connects that cell to this one. By making it a graph it removes the visual 'noise'. It exposes/demonstrates the bony structure behind the fleshy cells. It makes the logic precise & simple. Perhaps people don't accept the inability of 5 mutually adjacent points on a plane. I thought that was considered axiomatic. And it is not a cumulative property, ie. 2 sets of 4 mutually dependent points can't be in conjunction to create a higher dependency. Generally with more additional structure the dependencies are likely to include lesser dependencies such as 3 or 2. Maybe i am crazy, but once you see/understand the map as a graph structure it seems pretty apparent to me why you can't possibly have more than 4 cells mutually adjacent. |
|
Pythagoras
Quote | Reply | |
4 color map theorem
replied on: 3/15/2007 7:06:33 PM Actually, now that i read a little more on this problem, i think i would agree with you when you initially said that there is no proof of the 4 color problem! Philosophy. It looks like i'll have to do some thinking about the philosophy of "computer proofs" before i can say that i accept computer proofs of deep mathematical problems. I'm sure there's a place for the computer with respect to mathematical proofs...but to say that the computer has the last word!...maybe not. But now i see that there is such a thing as The 5 Color Theorem; with an accepted proof. ...i guess they went for the next best thing; 5. |
|
Pythagoras
Quote | Reply | This message was updated on 3/15/2007 7:14:32 PM by Pythagoras |
4 color map theorem
replied on: 3/15/2007 7:12:51 PM This site is exactly what i need!!!! Association and Motivation. I can't believe that with so so so many millions of Science and Math students all over the world with computers that so so few of them are here associating and getting motivation...and free answers to assignment problems too..ha. (they must not know that its here) Or maybe its just me being stupid. |
|
cramwit
Quote | Reply | |
4 color map theorem
replied on: 3/27/2007 12:58:51 PM On my illustration of how the entire plane is consumed/used by 4 topological triangles I should have specified that edge d-c is constructed out of [from] the points of NOT abc intersect NOT dab. I was thinking about the cycle-bifurcation rule/assertion & i am sure it works for all 'simple' 2D manifolds, such as a sphere or cylinder, but it doesn't work for a torus. [Perhaps it should be called a 'trifurcation rule' because there is the set of points that is the cycle itself as well as 'inside' & 'outside'] With a torus you can have cycles that echo the big 'O' or other ones that loop from the inside of the inner-tube to the outside of it that don't bifurcate the set of points. And interestingly you can also create a map that requires 5 colors by having two side-by-side loop ring patches of say yellow & red & then have 3 long patches [like a wrap around triangular prism] that contact both the red & yellow rings from the long way around the big 'O'. That creates 5 mutually adjacent cells on a torus map, requiring 5 distinct colors. |
|
cramwit
Quote | Reply | |
4 color map theorem
replied on: 3/27/2007 1:09:06 PM also on the torus if you think about both the non-bifurcating & bifurcating cycles if you stretch & warp them continuously [never losing cyclic self-connection] the non-bifurcating cycles will never become bifurcating, & the bifurcating cycles will never become non-bifurcating. Also i don't believe the loop ring cycles can become big 'O' cycles or visa versa. So i think it says you have 3 distinct sets of [simple?] cycles on a torus, which might work as a definition of its characteristics? |
|
cramwit
Quote | Reply | |
4 color map theorem
replied on: 3/27/2007 2:05:51 PM An easier way of imagining the 5 color map i mentioned above is take a long triangular prism with sides blue, green, & purple paint a ring on one end yellow & a ring of red on the other. Wrap the prism around so the yellow & red contact. A five color map. You can bifurcate a torus by using two non-intersecting ring-loops or two non-intersecting big 'O's. You can't have both a ring-loop & big 'O' cycle without them intersecting. Bifurcation of a torus is i think fundamentally its intersection with a simple planar space [not necessarily flat]. If you intersect it laterally it creates two ring-loops across the doughnut hole from one another & bifurcates the torus. If you intersect it with a plane parallel with the big 'O' you have an outer big 'O' & an inner, nested one one again bifurcating the torus. If you hit the torus from a near tangent on a 'corner' of it you get a single cycle that bifurcates the torus. If you take a cylinder & draw two lines along its length & color one part red & the other yellow you can match up the yellow to yellow as you wrap them around & create a bifurcated torus, but if you twist to match yellow to red as you wrap them around you have no bifurcation. So one half turn on the ring-loop axis matches yellow to red with no bifurcation & one full turn matches yellow to yellow creating bifurcation. So n + 1/2 turns = non-bifurcation & n full turns = bifurcated surface. |
|
cramwit
Quote | Reply | |
4 color map theorem
replied on: 3/30/2007 7:22:04 AM A 4 point mutual adjacency creates 4 triangle [3 point accessible] interiors that consume the plane. So the plane is sealed off with only 3 points accessible. Its construction is self sealing. A given triangle can have a mutual adjacency of 4 on its exterior & interior, but their '4th' cells/vertexes are both isolated [independent] from each other by the bifurcating triangle. Which allows the re-use of the same color. A 4 mutually adjacency inherently isolates one of its cell/vertexes, which is why it can never be cumulative. |
|
LinkBot
|
Gamers Wanted is looking for people to write game reviews and post news, |
|
|
| Tired of seeing ads? Click here to upgrade to Elite Membership! |
ChatArea.com Help & News Forums | Terms of Use | Contact ChatArea.com | Advertising
Powered By ChatArea.com - Get your free Society today! © Copyright 2003 Wewp!