View Full Version : Four Color Theorem

hhEb09'1

2007-Mar-17, 07:50 PM

[FONT=Georgia]I know, but as long as my counterexample stands (post 242, sorry, I'm not allowed to post hyperlinks to posts until I have a total of at least 30 posts), coming up with a proof is pointless, because you know the proof will fail and show that there is a counterexample.Ah. But a counterexample is a proof--that the method does not work! :)

I think grav accepts as common sense that any method that has a counterexample is not worth wasting time trying to prove that it works!

Also, that second diagramme on post 242 is for grav to colour with his revised method before he posts it, because that is the diagramme that caused Alfred Kempe's 1890 proof to fail.I was going to suggest 38! Something for grav to chew on. :)

However, we know that that map can be colored in four colors, so not all methods are going to fail on it.

Dragon

2007-Mar-17, 08:18 PM

38? You mean post 38? I don't see anything there.

---------------------------------------------------------------------------------------------------

38? You mean post 38? I don't see anything there.

01101001

2007-Mar-17, 08:40 PM

Hey Dragon, why don't you just make yourself an avatar if you want to see your posts quickly?

Here's one. This will certainly catch your eye, so, please, maybe, decorated text won't be necessary? Feel free to polish it to your graphical liking.

4922

hhEb09'1

2007-Mar-17, 08:53 PM

38? You mean post 38? I don't see anything there.For many years, the status of the theorem was that five colors were known to suffice, four colors were necessary, and every map of 38 regions or less was known to be four-colorable. Maybe I should have said 39 :)

PS: here's another possibility:

http://mensware.us/dragon3.gif

grav

2007-Mar-17, 11:04 PM

Well, it took me a while, but I finally figured out how to apply images. Just draw and color it in with Paint, save it in Pictures, and upload it from there with the staple-looking button when posting a reply. Pretty cool, really. Here is what the map should look like after the second run (ignore the last two images). We can now choose from areas 8 or 9.

Dragon

2007-Mar-18, 12:37 AM

Well, I thank you all for the avatars, but Dragon is just the username I used because the username I wanted to use was unavailable. Do y'all have any sites you know or something where I could find an avatar without copying someone else's? Where did you all obtain yours? Also, is this font more readable? Because if I use this font, I might as well switch to some other one, because it's still a habit to click the dropdown box and choose a font when I begin my post, and then I don't know which font to revert to.

On the other hand, grav, have you taken a look at my 1.bmp yet? It is the step-by-step derivation of 0.bmp.

Edit: I looked around for some avatars and found a few I wouldn't mind, but the size limits on this site are impossible. I have no clue how you all found avatars that would fit within this size limit. Not so much size, even, as the dimensions.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

Dragon

2007-Mar-18, 12:38 AM

For many years, the status of the theorem was that five colors were known to suffice, four colors were necessary, and every map of 38 regions or less was known to be four-colorable. Maybe I should have said 39

...

Actually, the largest size of map to be four-colourable changed a lot as different people came up with different techniques. It very well might have been known to be four-colourable with 38 regions for years, but it also has been known to be four-colourable with, say, 52 regions, 60 regions, etc. for different years.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

01101001

2007-Mar-18, 01:55 AM

According to The Journey of the Four Colour Theorem Through Time (http://www.calude.net/andreea/4CT.pdf) (PDF), they skipped right over the 38-region proof.

Franklin used unavoidable sets and

went further to prove in 1922 that a map with at most 25 regions is four-colourable. He was followed by

Reynolds who showed in 1926 that any graph with 28 regions is four-colourable. It is interesting to note

that the first book on graph theory appeared in 1936, published by König. The saga of regions continued

with 32 regions in 1938, proved by Franklin, 36 regions in 1940, proved by Winn, then Ore and Stemple

proved that any graph with 40 regions is four-colourable in 1970. In 1976, Mayer showed the same result

for a map with 90 regions.

grav

2007-Mar-18, 02:01 AM

On the other hand, grav, have you taken a look at my 1.bmp yet? It is the step-by-step derivation of 0.bmp.

Yes. I guess we're missing each other somehow. I posted the images in post #255. In the second run, rule #2 causes areas 2 and 3 to make area 8 the other two colors and areas 5 and 6 to make area 9 the other two for them. Then and only then can we apply rule #3 again, to either area 8 or 9.

Dragon

2007-Mar-18, 02:18 AM

OK, my 1.bmp is post 250. Take a look at it, revise it as applicable, and re-post it.

On the other hand, I use the WYSIWIG editor, and I still habitually change the font to fixedsys at the beginning (mostly because I still use fixedsys on other forums). If you don't want me to use Georgia (current font), please indicate which font you want me to use.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Mar-18, 03:08 AM

OK, my 1.bmp is post 250. Take a look at it, revise it as applicable, and re-post it.

Okay, then. Here it is. You can now choose a color for area 8 or 9.

Dragon

2007-Mar-18, 03:25 AM

How did you get 4 to be yellow?

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Mar-18, 05:09 AM

How did you get 4 to be yellow?

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.Oh, uh, I don't know how that happened, actually. :doh: Sorry about that. It should have stayed the same color. Here it is again, corrected.

grav

2007-Mar-18, 05:30 AM

I know, but as long as my counterexample stands (post 242, sorry, I'm not allowed to post hyperlinks to posts until I have a total of at least 30 posts), coming up with a proof is pointless, because you know the proof will fail and show that there is a counterexample. Also, that second diagramme on post 242 is for grav to colour with his revised method before he posts it, because that is the diagramme that caused Alfred Kempe's 1890 proof to fail. Chances are, that diagramme can make almost any false proof fail; I attach another diagramme that shows what Alfred Kempe's proof got the fc diagramme down to when it failed.

Edit: As you should be able to tell, he used a method slightly different from yours: he started with the points that have more than 5 areas touching them.Well, I've tried that last map five times in different ways and my method works for it so far, although I admit I missed applications for rule #2 a couple of times and had to backtrack, but that's my own fault, not a fault with the rules themselves. Here's an example. Each random choice I made is numbered. The last three areas in the final image can be colored any way one wishes using the possibilities available, still following the rules for them, though, of course.

01101001

2007-Mar-18, 05:42 AM

Each random choice I made is numbered.

You might want to remove random choices from your method. It would be easier to analyze if it were more methodical, even if the step is "now choose the alphabetically first of the available color choices". (Or was the randomness in the choice of next region? That could be methodical, too.) With random choices and back-tracking, it might be hard to show the method completes.

By the way, I don't see it. (Maybe I was distracted by all the text decoration. Ahem.) Did you state concisely your coloring algorithm? I saw it evolving, but did you ever state the final version?

Could you switch from using BMP files and go with (save as) something that can be displayed in-line, like GIF or PNG? I can't see thumbnail images with BMP, just filenames.

grav

2007-Mar-18, 06:15 AM

You might want to remove random choices from your method. It would be easier to analyze if it were more methodical, even if the step is "now choose the alphabetically first of the available color choices". (Or was the randomness in the choice of next region? That could be methodical, too.) With random choices and back-tracking, it might be hard to show the method completes.

By the way, I don't see it. (Maybe I was distracted by all the text decoration. Ahem.) Did you state concisely your coloring algorithm? I saw it evolving, but did you ever state the final version?

Could you switch from using BMP files and go with (save as) something that can be displayed in-line, like GIF or PNG? I can't see thumbnail images with BMP, just filenames.Yes, looks like I am going to have to remove the random choice thing anyway, actually. I just ran another version of that last map and it didn't work out, because of the "bridge" through the middle, I think. My original algorithm was kind of a "shortcut" since I noticed a pattern evolving, so I thought it might work out every time, especially after trying it in thirty or forty different ways on various maps, but apparently I'm not there yet, or at least not ready for shortcuts. I just thought it would be easier to explain and simpler to perform, but now that I can post images, I'm going with the much more rigid approach, which is that of the first two rules (from post #209), and what I described in post #238 for the third. I'm going to work it out in more detail and post again later.

[EDIT-Okay, I see what happened this time. I started with the first three colored areas on the outer edge of the map. Since we are actually trying to work our way outward, it's best to start with at one area in the inner most perimeter, counting down through successive complete perimeters from the outside (although this one has two, hence the bridge). It still doesn't matter, though. I'm going to get started on a more rigid algorithm (or see if rule #3 as posted in post #238 works for every case without getting stuck), one where all of the rules determine the colors of the areas in a specific way.]

worzel

2007-Mar-18, 12:21 PM

1) If a territory is bordered by any three territories that have different labels that have already been determined, then the territory that borders all three must have the fourth label.

2) If three territories all border each other, and two of them include the same two possibilities for their labels, then the third territory that borders them both does not include either.

Nice and simple so far.

Actually, that would be part of a proof for it, by trying every possible choice. That's actually how I found that this works in the first place, so I'll explain how that works as well. I just didn't want to get into all of that right off the bat since I knew rule #3 would be difficult to explain to begin with.

Okay. So here's what I actually did. I wanted a rigid proof, so I only eliminated possibilities according to rules #1 and #2, which are definite. It really doesn't matter what order those two are performed in. But after those two are exhausted, then what? Well, I took an area with two choices and tried a run for each one, placing the one I originally chose in a box and eliminating possibilities for other areas with a left to right diagonal slash through. I generally picked an area that had the most potential of eliminating possibilities for other areas, usually those with the most areas bordering it. Any other areas where the color was determined this way I also used a box around that possibility to show it. When all of the possibilities for rules #1 and #2 have been used, I then started back by setting a triangle around the other possibility for the same original area and doing the same thing with the other areas, this time eliminating possibilities with a right to left diagonal slash and setting triangles around the possibilities for other areas that are determined this way.

Now, after doing all of that, one can tell which possibilities for which areas can be determined to be a specific color, because they will have both a box and a triangle set around the same possibility for that area. So since the original area we started with led to the same possibility for another, and that is all of the possibilities for the original area, then any possibilities for any other areas that are both boxed and triangled must be definite, so the color for that area is now determined. Likewise, any possibilities for any other areas that contain a diagonal slash in both the left to right and right to left directions are therefore not used for either possibility in the original area, so those possibilities for the other areas are now crossed off. After doing all of this, we then start the run over. Now, I could have and probably should have explained it this way to begin with, but when I found a pattern that showed that using any possibility for any area on the outer perimeter with two possibilities came to the same conclusion, I started using that instead, and so far it has worked out every time.

But that's more like a journal than a rule :) Could you make a bit more concise?

I sounds like your current proposed method does require backtracking now that you've found an example where the simpler approach failed.

It would be very suprising if your method didn't work with backtracking because we already know that every map can be four colored somehow. But proving that your algorithm works everytime (with backtacking, that is) is the same thing as proving that if one doesn't break the rules along the way and keeps looking exhaustively one will eventually find a four coloring - sounds like we're back to square one to me :)

Dragon

2007-Mar-18, 01:45 PM

Grav, here's YOUR way of a diagramme, still showing a contradiction. Why do you not finish your diagrammes? I am getting very annoyed. This is the third or fourth time I have to finish a diagramme to show you that it still doesn't work. Work it out until the end next time, will ya?

On the other hand, on your proof, how did you go from 1b to 1c? I don't follow that step. I would much prefer it that you did the colouring of that diagramme like I did mine: show which colours are (are not) possible for every area: white means all are possible; a dark shade of a colour means only that colour is not possible; two colours mean they are both possible; also, if you save your diagrammes as a 16-colours bitmap and THEN as a JPG, you can cut your space usage about 12fold, and then you can afford to stick all of the diagrammes into a single bitmap (copy-and-paste, and then change), and that would simplify looking at the diagramme for us.

Last thing, if you do not like Georgia, please propose a font for me to use. "None" is not a choice on the dropdown box.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

hhEb09'1

2007-Mar-18, 04:09 PM

[FONT=Georgia]Last thing, if you do not like Georgia, please propose a font for me to use. "None" is not a choice on the dropdown box. One problem with using the dropdown fonts at all is that it makes it harder for the respondent to include context in their reply, without leaving orphan vB code scattered around. :)

Depends upon whether you want style or substance :)

01101001

2007-Mar-18, 04:21 PM

Attached Images

1i.bmp (http://www.bautforum.com/attachment.php?attachmentid=4944&d=1174225237)

People posting images, please use GIF or PNG, so I can see the thumbnail image in-line (and decide if it's worth displaying). It's not hard.

01101001

2007-Mar-18, 04:30 PM

Last thing, if you do not like Georgia, please propose a font for me to use. "None" is not a choice on the dropdown box.

Once you click the Fonts dropdown, then scroll down, scroll back up, scroll down again, scroll back up, look at all the pretty fonts you could have used, and then click the Fonts dropdown again, not a menu item, so the dropdown closes and you can just start typing your text using the same font everyone else uses.

Or, save time and stay out of the Fonts dropdown to begin with.

01101001

2007-Mar-18, 04:38 PM

I'm going to work it out in more detail and post again later.

Is it rude to ask what it feels like to think you've come up with a simple, elegant proof for a theorem that had resisted the attacks of generations of gifted hard-core mathematicians? What thoughts go through your head? Do you wonder why they all missed it? What do you gauge the probability of your being correct at? Are you looking forward to the fame and celebrity? What does it feel like?

hhEb09'1

2007-Mar-18, 04:56 PM

Is it rude to ask what it feels like to think you've come up with a simple, elegant proof for a theorem that had resisted the attacks of generations of gifted hard-core mathematicians? What thoughts go through your head? Do you wonder why they all missed it? What do you gauge the probability of your being correct at? Are you looking forward to the fame and celebrity? What does it feel like?I know this feeling :)

For me, I worry a lot, because the feeling crops up once a week, and it's only passed muster maybe six times. I started out in math grad school, so I early learned the hallmarks of where my errors tended to be--saved decades of time. I also realized that it was a good thing to succumb to objections, and learn from them, and then come back with a stronger case rather than committing myself to a weak case.

In fact, I wonder so much why they missed it that that forms half my research--going back and tracking those sort of things down. It can lead to amazing things in itself: one time, I came up with a dead-end, there was a two-year gap that I couldn't fill, and I had no idea whether something had happened in those two years that would negate my hypothesis. So, I called the office of Subramanyan Chandrasekhar, to get it from the horse's mouth, and he answered his own phone. Turned out, a geophysist had misread his paper, but Chandra had curtailed his own research in the area two years before so didn't notice the error. Fascinating.

hhEb09'1

2007-Mar-18, 05:01 PM

According to The Journey of the Four Colour Theorem Through Time (http://www.calude.net/andreea/4CT.pdf) (PDF), they skipped right over the 38-region proof.

Franklin used unavoidable sets and went further to prove in 1922 that a map with at most 25 regions is four-colourable. He was followed by Reynolds who showed in 1926 that any graph with 28 regions is four-colourable. It is interesting to note that the first book on graph theory appeared in 1936, published by König. The saga of regions continued with 32 regions in 1938, proved by Franklin, 36 regions in 1940, proved by Winn, then Ore and Stemple proved that any graph with 40 regions is four-colourable in 1970. In 1976, Mayer showed the same result

for a map with 90 regions. I had read a few books that mentioned the 38 figure (one is What is Mathematics, by Courant and Robbins, that I hold in my hands). Interestingly, I found the following on the internet (http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html)

Franklin in 1922 published further examples of unavoidable sets and used Birkhoff's idea of reducibility to prove, among other results, that any map with 25 regions can be 4-coloured. The number of regions which resulted in a 4-colourable map was slowly increased. Reynolds increased it to 27 in 1926, Winn to 35 in 1940, Ore and Stemple to 39 in 1970 and Mayer to 95 in 1976. I'm going to try to wade through the discrepencies. :)

worzel

2007-Mar-18, 06:36 PM

I've never had the feeling :(

Dragon

2007-Mar-18, 06:45 PM

People posting images, please use GIF or PNG, so I can see the thumbnail image in-line (and decide if it's worth displaying). It's not hard.

The problem with using those two filetypes, they reduce the quality of the image by compressing it. I wouldn't mind posting it hither in that filetype, but I want to retain the quality. I even tried to rename a BMP file to say .GIF so that it would show up as a thumbnail, but it said something along the line, "Incorrect file extension for the content". So when I download images to change, if it is saved as a GIF or whatever, I have to change it to a 16-colour bitmap, and then go back and delete all of the little gray and otherwise miscoloured dots resulting from the compression. If you would like, I can post two versions, a BMP and a GIF, so when you decide whether to look at something, you can decide from the GIF, but were you to edit an image to change it to the way you want it, and then have me do something with it, you can save a copy of it under BMP as well, so that its contents would not get distorted. The reason I did not do that is the same reason I stopped including a second copy of my post in my font: it seemed redundant.

Once you click the Fonts dropdown, then scroll down, scroll back up, scroll down again, scroll back up, look at all the pretty fonts you could have used, and then click the Fonts dropdown again, not a menu item, so the dropdown closes and you can just start typing your text using the same font everyone else uses.

Or, save time and stay out of the Fonts dropdown to begin with.But you see, I run a programme now that automatically selects fixedsys. It is very useful for other forums. So after I finish typing on this forum, I have to select my text, go to the dropdown box again, and choose a font thence. I cannot just delete the [font equals whatever], because it does not show up, as I am using a full WYSIWIG editor. If you tell me everyone else uses, say, Microsoft Sans Serif, I can choose that font when I change the font of my text. So that is why I asked for a font name that you wanted me to use. If afterwards I do not change it, it will remain as fixedsys, and apparently you all dislike fixedsys more than Georgia.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Mar-18, 06:54 PM

Is it rude to ask what it feels like to think you've come up with a simple, elegant proof for a theorem that had resisted the attacks of generations of gifted hard-core mathematicians? What thoughts go through your head? Do you wonder why they all missed it? What do you gauge the probability of your being correct at? Are you looking forward to the fame and celebrity? What does it feel like?Well, my last rule is definitely not elegant, just simple, but a little too simple apparently. It works out for the majority of cases, but not all without employing the more rough and tough method, so I'll still have to work on that. I could just use that method all the way through, but I think simplicity is the bottom line here. The problem is, though, choices do have to be made, since there is no one right way to do these. For each particular map, there are numerous ways the colors can be laid out, not counting the fact that the colors can be interchanged.

I actually expect this to happen much of the time, especially with the topics discussed on this forum. Usually, I can catch the problem area myself, but sometimes it's a little more subtle. Often, though, I just like to throw ideas out there and see how they hold up. It makes things interesting, and I learn a lot through the discussion, which can help the idea progress. I'll usually say beforehand that I am unsure or that things work out so far, basically meaning I have applied many cases and it has held up, so I haven't been able to disprove it, and I'm asking others to help disprove it with me. I don't count things such as this as a failure, or even a set-back. It's almost expected. I wouldn't want to continue to build upon an idea that doesn't work, but I don't just scrap it either. I try to pinpoint where it breaks down, figure out why that happens, and build up again from there, until I've closed all of the gaps. I don't know how these things could be done much differently, really.

As far as fame and celebrity goes, that's not the thing for me, although I guess it would be nice for a minute or two. But I am obsessed with figuring things such as this out for some reason, don't ask me why (it goes way back), and I would like to think that all of the time I spend on them is worth the while, by eventually coming up with something that will put my name in a history book or something after I am gone. Things can only be figured out once, and that's it, for the entire history of mankind. So if I were the one to figure something out that is worth noting and being remembered for, well, that would be just grand.

Oh, yeah. Plus the betterment of mankind thing and all that. :)

grav

2007-Mar-18, 07:20 PM

Grav, here's YOUR way of a diagramme, still showing a contradiction. Why do you not finish your diagrammes? I am getting very annoyed. This is the third or fourth time I have to finish a diagramme to show you that it still doesn't work. Work it out until the end next time, will ya?

On the other hand, on your proof, how did you go from 1b to 1c? I don't follow that step. I would much prefer it that you did the colouring of that diagramme like I did mine: show which colours are (are not) possible for every area: white means all are possible; a dark shade of a colour means only that colour is not possible; two colours mean they are both possible; also, if you save your diagrammes as a 16-colours bitmap and THEN as a JPG, you can cut your space usage about 12fold, and then you can afford to stick all of the diagrammes into a single bitmap (copy-and-paste, and then change), and that would simplify looking at the diagramme for us.

Last thing, if you do not like Georgia, please propose a font for me to use. "None" is not a choice on the dropdown box.

Well, I wanted you to choose a color for either area 8 or 9 and we could continue from there, but I went ahead and included a few of the possibilities. I have noticed one discrepency in this map as well, though. We can't color area 8 green and then area 9 yellow. It doesn't work out that way. That's not bad out of at least thirty or forty possible ways this can be colored, but there's another rule to be had in there somewhere. It has something to do with an odd number of areas on the perimeter (after area 8 is colored) with the same two colors being used for all of them. I'll keep working on it.

grav

2007-Mar-18, 07:59 PM

On the other hand, on your proof, how did you go from 1b to 1c? I can choose a color for any two colored area, working inward from the outer perimeter of areas with two or three possibilities. The outer perimeter contains two areas to choose from so far, one on the very top and one to the far left. I chose the one on the far left and colored it with one of the two options for that area.

snarkophilus

2007-Mar-18, 08:27 PM

[FONT=Georgia]The problem with using those two filetypes, they reduce the quality of the image by compressing it.

Uh, no. Both GIF and PNG are lossless compression techniques. They are especially good for pictures with big blocks of colour, solid lines, et cetera. Maybe you are thinking of JPEG? (Though, I'm fairly sure JPEG level 1 is lossless, and it's still better than bitmap.)

Dragon

2007-Mar-18, 08:31 PM

I am sorry. Somehow I have a hard time communicating with you. If the attached thumbnails are the final products, then there are problems:

1. Adjacent areas 6 and 7 are of the same colour.

4. Adjacent areas 2 and 7 are of the same colour.

Now all you have to do is to come up with a way to end up with 2 and 3, not 1 and 4. Think on it, it is not that difficult.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

Dragon

2007-Mar-18, 08:49 PM

Uh, no. Both GIF and PNG are lossless compression techniques. They are especially good for pictures with big blocks of colour, solid lines, et cetera. Maybe you are thinking of JPEG? (Though, I'm fairly sure JPEG level 1 is lossless, and it's still better than bitmap.)

Okay, yes, you are right about the PNG, I was thinking JPG. But GIF did lose some things. I attach two images, a PNG and a GIF, of the same thing for you to look at more closely.

Edit: sorry, they are not clickable AND not magnified. I guess you'll have to click "Save As...", then open them with paint (because other image editors may glide right over the discrepancy), and last magnify to 8x (to see better).

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Mar-18, 08:54 PM

I am sorry. Somehow I have a hard time communicating with you. If the attached thumbnails are the final products, then there are problems:

1. Adjacent areas 6 and 7 are of the same colour.

4. Adjacent areas 2 and 7 are of the same colour.

Now all you have to do is to come up with a way to end up with 2 and 3, not 1 and 4. Think on it, it is not that difficult.Oh.. my... goodness. I can't believe I did that, twice even. Thanks. Just silly mistakes. On the last one, I somehow exchanged blue for yellow for area 7. I've edited the images in the post.

worzel

2007-Mar-18, 08:56 PM

But grav, you found an example yourself (with the bridge?) for which your algorithm didn't work for every possible choice, right?

Dragon

2007-Mar-18, 09:05 PM

But grav, you found an example yourself (with the bridge?) for which your algorithm didn't work for every possible choice, right?

 Yes, and not only that, but also your diagrammes 3 and 4 have the exact same final colouration. In addition, you must come up with some test that would tell you how to determine the colourations that would work rather than figuring them out by trial and error: that would get VERY time-consuming in huge maps.

[/font]

By the way, YES! I figured out a way for it to appear normal! All I have to do is to insert [backslash FONT] at the beginning of every post and at the end. What gave me that idea is that putting [FONT equals whatever] (with the =, of course) actually started a new font thing, so I figured so long as I did that with my post, it would work.

Edit: nevermind, it does not work with messages with carriage returns.

[font=fixedsys]Edit again: and it works even worse with more than 1 carriage return. 

[FONT=FIXEDSYS]═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Mar-18, 09:13 PM

Okay. Two more definite rules. I call them definite because they can't be any other way. Rules #1 and #2 are two so far. After studying where this went wrong a couple of times, here's two more. And don't worry, I've got images this time to demonstrate with. If an area with two colors are connected to two other areas with those same two plus one more, then that extra color cannot be used for an area that connects to both on the opposite side of them. The reason is that if we were to use that extra color for the opposite area, that would leave all of the three original areas with the same two color possibilities, which cannot happen. This is shown is the first image. Area 1 has two possibilities and is connected two two others, areas 2 and 3, with the same two plus one more. If we were to make area 4 that extra color (red), then all of the original three areas will have the same three possibilities left for their colors, but since there are three of them, then two possibilities won't work, of course. So the rule is that we must eliminate the extra color from the possibilities for the opposite area.

The next rule is that if an area is bordered by two territories that contain the same two possibilities, even though they aren't themselves connected, if those two are connect by a string of other areas that also contain the same two colors, and the number of areas along that string is even, then we must eliminate both possibilities of colors from the original area. This is because, if there is a string of the same two colored areas, and the number of them is even, then one end will end up being one of the colors and the other end of the string the other color, so that no matter which way one does it, both colors will end up bordering the original area, so both possibilities must be eliminated from that original area. The second image shows this. The string is that of the four with blue or yellow as possibilities, so areas 4 and 7 that both border area 9 will be blue and yellow regardless, so area 9 cannot be blue or yellow. This eliminates yellow as a possibility for area 9.

snarkophilus

2007-Mar-18, 09:14 PM

[FONT=Georgia]Okay, yes, you are right about the PNG, I was thinking JPG. But GIF did lose some things. I attach two images, a PNG and a GIF, of the same thing for you to look at more closely.

GIF is only 256 colours, so if you're using more than that, then you will run into trouble. Also, if you're not using the standard palette, you'll need to choose a custom one when you save the file. In most cases, it's more efficient just to use PNG.

Really, if you can demonstrate that you have a real, working proof of the 4CT, I won't mind if it's bitmaps. :)

Dragon

2007-Mar-18, 09:19 PM

GIF is only 256 colours, so if you're using more than that, then you will run into trouble. Also, if you're not using the standard palette, you'll need to choose a custom one when you save the file. In most cases, it's more efficient just to use PNG.

Really, if you can demonstrate that you have a real, working proof of the 4CT, I won't mind if it's bitmaps. :)

 Actually, the bitmap I was using was using only 16 colours (in reality, 8). 

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Mar-18, 09:27 PM

Okay, so with the two extra rules from post #286, we now have four definite rules. These will apply no matter what, and can be done in any order. So only after all of those are exhausted can we choose one randomly from the outer perimeter, since there would be nothing else requiring a specific color to be chosen, whereas there are many possible ways to color these maps. Let's see if anyone can disprove it now. If they do, another rule must be applied, but this is the algorithm as it stands so far.

Dragon

2007-Mar-18, 10:38 PM

OK, grav, you do realize that when I tell you to show an example, I mean show it through til completion. I am tired of wasting hours taking your examples to completion to find that they fail. I will do it this one last time and show you how to show that it works for that particular image, but next time, please do it yourself. I have other things to do, you know. Please, please, please, learn from this graph how to show that your way works always to colour this specific graph. I attach a progress that shows how to show that your way works to colour -.png; now show you can colour fc in the same way you did (also attached).[/font]

Edit: the "attached images" are actually the first two files in the proof; they were not clickable as PNGs or GIFs, so I had to upload them as BMPs.[font=fixedsys]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

Dragon

2007-Mar-18, 10:41 PM

The remainder of the files in the proof.

Edit: for the proof, to go from file to file, you may (these are my rules for proving that a map is colourable using your proof):

1. Apply any amount of rules 1 and 2 and colour all areas with possible colours.

2. Apply any amount of rules 3 (w/ only one way to do it)(not on my examples).

3. Apply any amount of rules 4 (not used on this map).

4. Rearrange the maps (systematically).

5. Choose an area with multiple possibilities for application of rule 3 and split them up.

6. Remove any maps derived from map X in file A, on which rule 3 was not used in step 5, but only so long as rule 3 was used on one of the maps that were derived from the same map X in file A (not shown)

i. e. if you're applying rule 3 to area 8 based on areas 7 and 9, and if 8 has RGB, 9 has RB, and 7 has BY, you will end up with: 7=>8: 8 has RGB; 9=>8, 8 has Y. Therefore, since 8 was not changed in 7=>8, and since 8 was changed in at least one combination of rule 3 onto this map, you can remove 7=>8, but that needs a step to itself, even before recombining the areas.

And you know, that's what I did before, except I didn't show it, but I rather just used one of the examples that came up white to show you that your proof didn't work. So now, as to my maps:

╔═══════╦════════════════╗

║To get║Use my rule №║

╠═══════╬════════════════╣

║0 ║1 ║

║1 ║5 ║

║2 ║1 ║

║3 ║5 ║

║4 ║1 ║

║5 ║4 ║

║6 ║5 ║

║7 ║1 ║

║8 ║4 ║

║9 ║1 ║

║a ║1 ║

║b ║1 ║

╚═══════╩════════════════╝

Now if you can show how to colour fc this well, using the same procedure that I outlined, I will tell you what to do next to show whether or not it works for all maps.

Does code show up this well on your computers? Because for my computer, code shows up as fixedsys, so it appears aligned. Is it so on your computers?

[/FONT]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Mar-18, 11:33 PM

I'm afraid I'm not sure what you're asking, Dragon. About every possibility there is for that first graph after the first three areas are chosen and colored in and after choosing red for #1 is in post #278 (after editing). And I hate to say it, but none of the images you posted just now follow the rules for choosing a color. It has to be from a two possibility area. All of the ones you chose have three. I thought you understood that. That means you can choose a color for area 1, 3, or 5 after the first run.

Dragon

2007-Mar-19, 12:06 AM

But I was following your rule №3. Because apparently, it works, and just "choosing from two colours" doesn't. In addition, by showing that you can apply rule 3 to a territory in any way possible and still have it work shows that this map cannot be not coloured using that rule.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Mar-19, 12:57 AM

But I was following your rule №3. Because apparently, it works, and just "choosing from two colours" doesn't. In addition, by showing that you can apply rule 3 to a territory in any way possible and still have it work shows that this map cannot be not coloured using that rule.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.Rule #3 is that you look at all of the outermost perimeter of two and three colored areas, ignoring those with four (white), and pick one with two. Then pick one of the two possibilities for that area to color it with. If the outermost perimeter contains only three color areas, then ignore those and pick from the next perimeter in.

grav

2007-Mar-19, 01:08 AM

Okay. Another rule, but this one is a little more complicated, I'm afraid. I'll see if there is a way to bypass it beforehand or something, so it doesn't occur in the first place, but for now it stands. It is similar to the string of areas with the same two colors rule. If we have an odd number of areas that produce a string of the same two colored areas, and the ends of which loop around and meet with two other two colored areas with one of the same colors each, and those two areas border each other and a third two colored area with the same two other colors besides the one the other two have in common, then the two ends of the string must be the color the two at the ends do not have in common. Yeah, I know. Please don't even ask me to try to say that again. Anyway, maybe this image will help.

In the last one, areas 4, 7, and 8 create an odd numbered loop of two colored areas with the same two colors. The string ends at areas 5 and 6, which also contain one of those colors in common, green. But they also border area 9, which contains each of their colors besides the one they have in common. This means that area 5 can't be blue and area 6 red at the same time because that would leave no colors for area 9. So one of the areas 5 or 6 must be green. This in turn means that neither area 4 or 7 can be green, because if it is, it will circle around the string so that the other is as well, and we would have green on both sides, which would then border areas 5 and 6, one of which must also be green. In that case, both areas 4 and 7 must be yellow.

That makes five definite rules in all so far that must be applied regardless of the algorithm used, if they occur. There may be more to come. I'll keep checking. Since there's a little leeway, I'm also going to see if there is a way we can choose colors that keeps any such strings from forming in the first place, in order to bring the number of rules down and to keep things as simple and neat as possible.

Dragon

2007-Mar-19, 01:33 AM

I thought you changed your rule №3... Now, regarding your new post: OK, once again you're showing a picture of what the rule is, but not only are you not following the picture through until completion, but also you're not showing that it works for every single possibility of application of that rule. I am sorry, but I am quite tired of wasting hours upon hours trying to show you the different possibilities that would either make your rule work or not work. Please do it yourself, like I had done in the post before, the one with pictures going from - to b. So just to iterate this, I am going to stop looking at your rules if you do not do what I did before. Because what's happening, you're spending 5 minutes to come up with a rule, and then I spent 2 hours to show whether or not it works.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

Dragon

2007-Mar-19, 01:37 AM

I'm afraid I'm not sure what you're asking, Dragon. About every possibility there is for that first graph after the first three areas are chosen and colored in and after choosing red for #1 is in post #278 (after editing). And I hate to say it, but none of the images you posted just now follow the rules for choosing a color. It has to be from a two possibility area. All of the ones you chose have three. I thought you understood that. That means you can choose a color for area 1, 3, or 5 after the first run.

But you see, you only show the possibilities that work: what you're NOT doing is showing EVERY possibility, even the ones that work; and even if you were, you have to be systematic in how you got them. Check out my last and next-to-last posts with diagrammes: THAT is systematic.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Mar-19, 02:19 AM

But you see, you only show the possibilities that work: what you're NOT doing is showing EVERY possibility, even the ones that work; and even if you were, you have to be systematic in how you got them. Check out my last and next-to-last posts with diagrammes: THAT is systematic.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.I think you're misunderstanding my posts. I have been systematically going through possibilities, but as I'm sure you know, since you have been working through these also, there are many ways to color in the maps, so showing where it works out would require an awful lot of possible combinations. I am just concentrating on where it breaks down, finding out why it did so, and discovering the rules accordingly. The last few images only demonstrated the algorithm up to the point where it breaks down, and the rule that must be applied under those circumstances. I am not making up rules willy-nilly, though. These are concrete rules that must be followed for any algorithm, as I find them and see how things must absolutely go. Only rule #3 has any leeway otherwise, so there is still some room to work with. The rest of the rules must be followed regardless of who comes up with what algorithm, unless the algorithm eliminates some of the conditions that the rules apply to in the first place, rendering them unnecessary, which is what I am now attempting to do. Anyway, here is the completed version for the last image I posted, with rule #5 applied. The last two parts consider two possible outcomes.

Dragon

2007-Mar-19, 02:27 AM

OK, sorry, perhaps I'm not making myself clear enough. http://www.bautforum.com/showthread.php?p=950412 is where I outlined the rules of systematically; http://www.bautforum.com/showthread.php?p=950408 is where I started to show you how to work out a problem systematically using the four rules you had at that time, using 13 images. I also gave you a fourteenth image for you to practice working out your systematicity. But instead, you came up with a new set of rules. If you can work out your new set of rules the same way I did starting at http://www.bautforum.com/showthread.php?p=950408, then you will see whether or not your set of rules works. Then if it does, you can post your 13 (or more or less, depending on the rules) images that show that your rules work. Only then will I be willing to think of a formal proof.

By the way, YES!!! Now I have enough posts to post links!

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Mar-19, 03:13 AM

OK, sorry, perhaps I'm not making myself clear enough. http://www.bautforum.com/showthread.php?p=950412 is where I outlined the rules of systematically; http://www.bautforum.com/showthread.php?p=950408 is where I started to show you how to work out a problem systematically using the four rules you had at that time, using 13 images. I also gave you a fourteenth image for you to practice working out your systematicity. But instead, you came up with a new set of rules. If you can work out your new set of rules the same way I did starting at http://www.bautforum.com/showthread.php?p=950408, then you will see whether or not your set of rules works. Then if it does, you can post your 13 (or more or less, depending on the rules) images that show that your rules work. Only then will I be willing to think of a formal proof.

By the way, YES!!! Now I have enough posts to post links!

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.Okay. I think I see where we are bypassing each other here. I hope, anyway. :) Forget the algorithm for a minute. Let's concentrate on the rules, which includes five, minus #3, which is really just taking the next step by choosing a color once all mandatory eliminations have taken place by following the rest of the rules. So I won't call rule #3 a rule anymore, just a step to take in order to start the next run. The way I figure it, if all mandatory operations are performed that eliminate all of the possibilities that cannot be had for a particular area, then almost any of the remaining possibilities may be chosen and then the same rules applied again when considering that new colored area.

Okay. So here's the thing. I'm not trying to see if the rules work out, I know they work. That's why they are mandatory. If they are not followed to the letter, the coloring will not work. So what I'm doing now is to try to find out all of the mandatory rules I can and then I will see if there is a way to choose the colors after all of the rules have otherwise been exhausted in such a way that the least number of rules must be applied. So regardless of the algorithm used, these rules must be applied if the given situation arises or it won't work out. So finding a proof for this theorem would probably mean finding all of the rules that must be applied regardless, unless one can find an algorithm in which some of them are unnecessary. In other words, I am not trying to show if the rules work, since if they are not applied, the coloring definitely won't work out, but I'm trying to see how many rules there actually must be, and then see if there is a way to get around them with some simple algorithm, although I am still using my original one for now in order to find them.

For example, consider rule #1. If three areas, each with a different color, all border a fourth, then the fourth area must have the fourth color. That is mandatory, no way around it, especially since that is what we are trying to prove in the first place. Rule #2 says that if any two areas which have the same two possible colors and border each other, then any other area they both border simulataneously must not have either of those colors as possibilities. Again, mandatory, regardless of the algorithm used. If it weren't, then three areas that border each other could have two of the same color, which of course they can't, given the circumstances of the theorem itself, as with the first rule. The other three rules so far apply similarly. No matter what algorithm you or I or anyone else comes up with, these rules must apply when those conditions arise.

So I am actually still a very long way from a proof, and not doing too bad with the algorithm, but still not there yet. I just have to keep concentrating on finding all of the rules that must be applied until I have them all, assuming a limit even exists. It's possible that more and more complex, yet rare, rules must be applied under very special circumstances or something, but I'm hoping not. So after I think I've found them all, that is actually what must be proven first.

Can you or anyone else come up with any other rules that must be applied no matter what for a given situation? Let's start with that.

grav

2007-Mar-19, 04:03 AM

You know, I'm probably going to end up cheating with this. It would just take too long to apply colors in every way imaginable to various maps to find out which rules must be applied under given circumstances. I made a program once that played the game 'connect four' against itself by starting out with random moves when it switched to each side. After each game, points were subtracted from whatever moves that led to a loss for the one side according to the circumstances involved, and added for the moves for the side that won, but placed into the same memory. After a few hundred such games, I played against it myself and ended up losing seven out of ten games.

I might try the same thing with this, although it might take a while. I can make random areas on the screen and have the computer fill them in, randomly at first, and then according to its program as points for certain moves are added or subtracted, depending on whether it fills in the entire area or not. I will probably have to start with simple areas for it and then get more complex as it learns which ways work best. If it gets to the point where it can fill in all of the areas every time, then I can just "pick its brain" to see how it is doing it.

If I do that, though, would it be considered cheating, or would I still get credit for it? :neutral:

Dragon

2007-Mar-19, 04:04 AM

OK, sorry, I am too sleepy for now, but when I say "your rules work", I don't mean that they are not mandatory: I just mean that they are not sufficient to provide a full colouration of a graph. The pictures in the post mentioned above showed that these rules were sufficient to colour that one graph, in this order:[/FONT]

1. Start out with three colours.

2. If an area has a region definitely coloured adjacent to it, that area cannot be the colour of the adjacent area.

3. If an are only has one possibility for a colouration, it is that possibility.

4. If an area has two possibilities and another area has those two possibilities and a third one, colour the other area with that third colour.

However, these are not sufficient for all graphs. So I showed you how to show that certain rules are sufficient for a graph. Your job now is to check your new rules against the fc.png graph to make sure that they work BEFORE posting them here, and showing that they do work when you post them.

Now here is something else: you don't have to show all the possible colourations for EVERY area: if you notice what I did, I just picked one territory and showed all the possibilities for it, and when I could do no more, I picked another area and showed all the possibilities for it, etc. It is a rule that if one area at a time is followed, that is sufficient to show that the same would work for any combination of areas in the same circumstances one area at a time.

Also, the only reason the current four-colour proof does not get credited by some is because there is no way to extract it from the computer in a way that would be followable by people.[font=fixedsys]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Mar-19, 05:12 AM

OK, sorry, I am too sleepy for now, but when I say "your rules work", I don't mean that they are not mandatory: I just mean that they are not sufficient to provide a full colouration of a graph. The pictures in the post mentioned above showed that these rules were sufficient to colour that one graph, in this order:[/FONT]

1. Start out with three colours.

2. If an area has a region definitely coloured adjacent to it, that area cannot be the colour of the adjacent area.

3. If an are only has one possibility for a colouration, it is that possibility.

4. If an area has two possibilities and another area has those two possibilities and a third one, colour the other area with that third colour.

However, these are not sufficient for all graphs. So I showed you how to show that certain rules are sufficient for a graph. Your job now is to check your new rules against the fc.png graph to make sure that they work BEFORE posting them here, and showing that they do work when you post them.

Now here is something else: you don't have to show all the possible colourations for EVERY area: if you notice what I did, I just picked one territory and showed all the possibilities for it, and when I could do no more, I picked another area and showed all the possibilities for it, etc. It is a rule that if one area at a time is followed, that is sufficient to show that the same would work for any combination of areas in the same circumstances one area at a time.Okay, good. I think we are on the same page now. I tend to work backwards with these sort of things, though. What I want to do at this point is to compile a list of all mandatory rules that must be applied no matter what, and then later to find an algorithm for choosing colors for areas in such a way that the least number of rules may be applied, which is the same thing you're saying, but I'm kind of coming at it from the other direction, I think. In other words, instead of using an algorithm at all for this, we could just color the territories randomly and see where we get into trouble each time, find the rule that would prohibit coloring that way depending on the circumstances, and then apply that rule and any others we have already found with each run until there are none left to keep us from coloring an entire map in randomly, except for wherever those mandatory rules must be applied, however many there turn out to be. And the rules wouldn't just be something we come up with that just happens to work out for a particular situation or something, but it must be absolute, a rule for what we definitely cannot do, so that it can be proven to be so, as with the five rules so far, and this would also help when coming up with a proof for the theorem.

Also, the only reason the current four-colour proof does not get credited by some is because there is no way to extract it from the computer in a way that would be followable by people.[font=fixedsys]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.That's true. If I make a program for it, I would have to set it up in a way that when I go through it afterwards, I would be able to pinpoint exactly what it is doing each time. It won't be easy.

Dragon

2007-Mar-19, 05:23 AM

No offense, but you can also work on expressing a rule as briefly as you can. Did you see how concisely I explained yours in my previous post? See if you can do the same with all of your five rules now. Attempting to do so without looking at my rules would help you do the same for any new rules you come up with. By the way, the rules I named do not work by themselves for the fc graph: more rules are needed; and since fc failed the Kempe's original 1890 proof, it certainly is a good map to experiment with for any future rules. In fact I'm fairly sure that even all the rules you currenty have can fail one way or another trying to colour fc. So go ahead and try to see how much failures you can obtain, and if you ever think up of a set of rules that you can't fail colouring fc with, you can post them here (concisely, once again) so that I could try, and if I can't, then we both can work on eliminating redundant rules.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

worzel

2007-Mar-19, 09:44 AM

I might try the same thing with this, although it might take a while. I can make random areas on the screen and have the computer fill them in, randomly at first, and then according to its program as points for certain moves are added or subtracted, depending on whether it fills in the entire area or not. I will probably have to start with simple areas for it and then get more complex as it learns which ways work best. If it gets to the point where it can fill in all of the areas every time, then I can just "pick its brain" to see how it is doing it.

If I do that, though, would it be considered cheating, or would I still get credit for it? :neutral:

Neither. The computer program itself would prove nothing. Picking its brains to see how it works will just give you a long list of rules like list you're compiling now. You'd still have to attempt to prove that your list is sufficient before anyone's even going to bother looking at it.

PS There's nothing wrong with using a computer to help you find a tentative set of such rules. The use of a computer in the successfull proof of the theorem was different - they already proved that there were only so many cases to check, then programmed a computer to systematically check all those cases.

grav

2007-Mar-19, 03:55 PM

Neither. The computer program itself would prove nothing. Picking its brains to see how it works will just give you a long list of rules like list you're compiling now. You'd still have to attempt to prove that your list is sufficient before anyone's even going to bother looking at it.

PS There's nothing wrong with using a computer to help you find a tentative set of such rules. The use of a computer in the successfull proof of the theorem was different - they already proved that there were only so many cases to check, then programmed a computer to systematically check all those cases.Actually, I think I've changed my mind about that, after thinking about it for a while. I might do it eventually, just for kicks, but coming up with a program that can learn well enough and in such a way that I can go through it afterwards to see what its doing would be quite a chore, and may take weeks or months. I can pretty much tell what goes wrong when I get stuck, and find the mandatory rule that applies accordingly, so I guess I'll just program in the rules as I find them and let the computer run through various maps randomly while running through the rules after coloring each area. If it gets stuck, I'll look through the map and see why, and I'll have a new rule. I can then see if there might be an algorithm that reduces them. I'll definitely need to write a program for this much, at least, so I can quickly run through all possible combinations for a particular map, which would take a tremendous amount of time otherwise. And if anyone else comes up with an algorithm they think works, I could also check that for them.

I'm thinking the number of mandatory rules, which can be run in any order without affecting the others, and would be applied with or without an algorithm if that particular situation arises, would be limited. This is the case if considering only the possibilities for three bordering areas, two of which have the same possibilities for their colors, or at least, that's what I see so far. All of the rules I've come up with include one area with two others that border it, although directly or indirectly through a chain or otherwise, that have the same two possibilities for their colors, so I may be able to eventually prove that all possibilities are accounted for, and if I can do that, I would be just a jump away from a proof for the theorem itself.

worzel

2007-Mar-19, 04:49 PM

Well good luck with the final little jump :)

hhEb09'1

2007-Mar-19, 05:02 PM

Okay. So here's the thing. I'm not trying to see if the rules work out, I know they work. Not quite. Only the ones that you called "common sense"--because those are the ones that we can easily prove that a violation of the rule would result in a failure. The other rules, you do not know that they work. They may or may not.

Can you or anyone else come up with any other rules that must be applied no matter what for a given situation? Let's start with that.Add "use only four colors" to your list :)

I'm thinking the number of mandatory rules, which can be run in any order without affecting the others, and would be applied with or without an algorithm if that particular situation arises, would be limited. I would bet that if you could prove that the number of rules was limited, you would have accomplished most of the effort needed to prove the theorem.

and if I can do that, I would be just a jump away from a proof for the theorem itself.Well, as I say, I think that is where most of the work is. :)

You're probably .001% finished. :)

snarkophilus

2007-Mar-19, 08:03 PM

I'm not trying to see if the rules work out, I know they work. That's why they are mandatory. If they are not followed to the letter, the coloring will not work. So what I'm doing now is to try to find out all of the mandatory rules I can and then I will see if there is a way to choose the colors after all of the rules have otherwise been exhausted in such a way that the least number of rules must be applied. So regardless of the algorithm used, these rules must be applied if the given situation arises or it won't work out. So finding a proof for this theorem would probably mean finding all of the rules that must be applied regardless, unless one can find an algorithm in which some of them are unnecessary.

This is probably quite similar to what the guys who originally solved this thing did, and it looks like the right way to approach it. (The accepted proof is down to about 600 "rules" that must be met. I have a feeling that your rule set is going to get very big, and quickly.)

Even if you accept that, it's probably still worth playing with, though. What if you could find a rule that reduced some of those 600 cases into a single case? You'd have reduced the current proof in size, which is pretty significant.

Dragon

2007-Mar-20, 01:07 AM

This is probably quite similar to what the guys who originally solved this thing did, and it looks like the right way to approach it. (The accepted proof is down to about 600 "rules" that must be met. I have a feeling that your rule set is going to get very big, and quickly.)

Even if you accept that, it's probably still worth playing with, though. What if you could find a rule that reduced some of those 600 cases into a single case? You'd have reduced the current proof in size, which is pretty significant.

It would probably help to obtain the set of 600 rules and then look at whether you're going the correct direction.

peter eldergill

2007-Mar-20, 02:46 AM

Grav, I'm sure you probably understand the problem better now than you ever thought you would, don't you (or better than you cared to know it! HA!)

Honestly, I haven't read most of the posts, but I find the problem very intersting.

Pete

grav

2007-Mar-23, 11:41 PM

Okay, I have finally written a program for that 'fc' map. I only put in those first two mandatory rules to start with for the trial run, though. It only works a little better than about three-quarters of the time for just those two. The program can color the entire map four or five times per second, very much faster than I was doing, so that's pretty good, right? Well, as it turns out, it's still not quite good enough. I've been waiting half the day for the program to run through all of the possible ways for doing it, and now I realize why it's taking so long. With only twenty-five areas to fill in with one of four different colors, there are about a million billion combinations. Considering also the orders that they can be colored in one by one in any particular order drives it up to about possible 10^40 combinations for color and order of coloring of each area. Now, once the rules are applied to the algorithm I've been using, there still seems to be about 1.2 billion combinations possible. Figuring four or five done per second, it should only take about 8.5 years to run the program all of the way through, and adding more rules would require it to take that much longer. I'm definitely going to need a more efficient algorithm. Any suggestions?

hhEb09'1

2007-Mar-24, 05:22 AM

Any suggestions?Maybe start with Appel and Haken? :)

worzel

2007-Mar-24, 10:52 AM

I thought the extra rules beyound the first two were to reduce the number of times when you had to make a random choice. Each extra rule's flavour was to take some more definite action before having to resort to arbitrarily chosing a perimeter territory and arbitrarily chosing a color for it. If so then adding the extra rules should reduce rather increase the number of cases to test for each map.

But all that's rather moot when you've still got infinite maps to check :)

grav

2007-Mar-24, 04:29 PM

Maybe start with Appel and Haken? :)

Thanks. I generally like to try to work things through on my own, and only resort to checking out other people's methods at times when I've gone as far as I can go, or get stuck. I guess this would be the time. :)

grav

2007-Mar-24, 04:40 PM

I thought the extra rules beyound the first two were to reduce the number of times when you had to make a random choice. Each extra rule's flavour was to take some more definite action before having to resort to arbitrarily chosing a perimeter territory and arbitrarily chosing a color for it. If so then adding the extra rules should reduce rather increase the number of cases to test for each map.

But all that's rather moot when you've still got infinite maps to check :)I meant that adding more rules would take up more program time to go through each one, making it take even longer to run, but now that you mention it, it would make for less arbitrary choices, so less overall run-throughs, whereby it might take roughly the same time or possibly even less, you're right. But I'm thinking more along the lines of a starting point that limits the number of areas we can begin with. For example, if we start with the inner most perimeter, by subsequently eliminating all outer perimeters until we get down to the last few areas, then there is only one area in the 'fc' map, anyway, we can use to color in our first area, and then we can add two of the adjoining areas to that.

01101001

2007-Mar-24, 05:48 PM

I meant that adding more rules would take up more program time to go through each one, making it take even longer to run, but now that you mention it, it would make for less arbitrary choices, so less overall run-throughs, whereby it might take roughly the same time or possibly even less, you're right.

The Wikipedia article mentioned that coloring algorthims use O(n2) time. 20 regions should take about 4 times as long as 10. If you're seeing worse scaling, it would indicate you've got a fundamental problem.

I'm not sure why you are after efficiency. It shouldn't affect any proof of the theorem by algorithm. Logical arguments don't depend on execution speed. Is it that you don't actually have an algorithm and you are trying to evolve one? I'm not optimistic that you'll generate a theorem-proving algorithm by tinkering with coloring heuristics. It might be better to have a plan. Discovering a particular algorithm may not, probably won't, quickly translate to a proof.

grav

2007-Mar-25, 06:45 PM

The Wikipedia article mentioned that coloring algorthims use O(n2) time. 20 regions should take about 4 times as long as 10. If you're seeing worse scaling, it would indicate you've got a fundamental problem.You'll notice that says that efficient algorithms have been found that require only o(n2) time. Mine is not that efficient. If we figure all of the possible ways to color in 25 areas, as with the 'fc' map, then there are 4^n=4^25=10^15 possibilities. If we also figure all of the different orders in which they may be colored in one at a time, that is 25*24*23*...=n!=25!=10^25 possiblilities for that. Altogether, with the possibilities for the orders of the areas and the choice of color each time, this makes a grand total of 10^15*10^25=10^40 in all! Now, my logarithm and the two main rules reduce this tremendously to only about 1.2 billion estimated possibilities to be accounted for with the 'fc' map, but it would still take 8.5 years to run them all.

I'm not sure why you are after efficiency. It shouldn't affect any proof of the theorem by algorithm. Logical arguments don't depend on execution speed. Is it that you don't actually have an algorithm and you are trying to evolve one? I'm not optimistic that you'll generate a theorem-proving algorithm by tinkering with coloring heuristics. It might be better to have a plan. Discovering a particular algorithm may not, probably won't, quickly translate to a proof.Well, since there are actually multiple ways a map can be colored in, so no one right way, I was going to try to find all of the mandatory rules that must be followed no matter what, and whatever was left can be colored in any way that is otherwise allowed. These are only the absolutely mandatory rules, though, so much, much less than the 600 or so the others came up with. But that still means I have to run through every possibility imaginable, while following those rules, and I don't want to wait eight and a half years for the computer to run through a single map, so I have to limit the choices somehow, which means coming up with a more efficient algorithm that might allow for just a few of the choices but not all. So you're right, then. I do need a better plan.

grav

2007-Mar-25, 06:48 PM

Grav, I'm sure you probably understand the problem better now than you ever thought you would, don't you (or better than you cared to know it! HA!)Oh yeah. :)

HenrikOlsen

2007-Mar-25, 07:04 PM

Well, since there are actually multiple ways a map can be colored in, so no one right way, I was going to try to find all of the mandatory rules that must be followed no matter what, and whatever was left can be colored in any way that is otherwise allowed. These are only the absolutely mandatory rules, though, so much, much less than the 600 or so the others came up with. But that still means I have to run through every possibility imaginable, while following those rules, and I don't want to wait eight and a half years for the computer to run through a single map, so I have to limit the choices somehow, which means coming up with a more efficient algorithm that might allow for just a few of the choices but not all. So you're right, then. I do need a better plan.

Especially since using those 8.5 years still wouldn't prove that the rules would always be sufficient for any map, so you wouldn't actually be closer to a proof.

grav

2007-Mar-25, 07:34 PM

Especially since using those 8.5 years still wouldn't prove that the rules would always be sufficient for any map, so you wouldn't actually be closer to a proof.That's true. Even after I come up with a set of mandatory rules that must be used to color in any map I've used so far, I would still have to prove that that no others would be required to color in a different or still more complex map before I could go any further. Oh, the humanity! :doh: :wall: :o :rolleyes: :)

01101001

2007-Mar-25, 07:59 PM

You'll notice that says that efficient algorithms have been found that require only o(n2) time. Mine is not that efficient.

I'm beginning to believe that, but no, I didn't know how efficient yours was. I didn't even know if you knew, so I pointed out a benchmark, something to aim for, a target that when not met means something serious is wrong. Hope it helped.

It sounds like you are now doing enough thinking to "color" your first published optimistic thoughts on the matter. It's a seductive problem, difficult, deep, yet so simple and charming to describe, almost appearing trivial to conquer. I doubt any serious mathematician avoided taking a stab at it, from its existence until the first correct proof was announced. Each of them, save Appel and Haken, failed.

So, congratulations on the progress, even if it wasn't where you'd expect it to lead. Thanks for having a good attitude about it.

hhEb09'1

2007-Mar-26, 02:23 AM

Thanks for having a good attitude about it.grav doesn't need to be led to the water, he's great about that. Still, there's the drinking part... :)

Dragon

2007-Mar-26, 03:57 AM

Sorry, I've been gone away to NRAO for the weekend and couldn't write back sooner, as they don't allow electronics, especially with radio waves. The problems you're having are very unnecessary. Basically, because the first two rules are necessary no matter what, the combination of the first two rules used does not change the outcome, so you need not bother worrying about checking the order of application of the first two rules, as you should be able to see from my post where I showed all the combinations of colouring your 12-region map to show that they worked on that particular map. Instead, focus on combination of application of the other rules; moreover, they need not be applied to more than one area at a time: i.e. you don't have to show that you can colour, say, area 5 and then area 2, and also area 2 and then area 5; either order would show that it is colourable so long as you include all the possible colourations of area 5 versus all possible colourations of area 2. As you should have seen, the 12-region map had few enough combinations like that to allow me to show by hand that it is four-colourable within your rules. Now that I showed you where your programme was wrong, you can revise it.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Apr-04, 04:00 AM

In case anybody's wondering, I'm still working on this. I've realized from the comments on this last page that I do need a completely different approach, and I think I've come up with a more plausible one. There is only one rule involved, and I believe it would be easier to prove it works.

Instead of proving that a given set of rules is always enough, which I'm not sure I could, and working with all possible relationships between areas, I've narrowed it down a little for now. At this point, I only wish to prove it for a map that contains only triple vertices, where three areas come together at a point, no more and no less. All of the maps that we have considered so far do this, except that the map of the US contains one point where four of the states come together. With this type of map, only one rule is necessary with the method I will use. We will start by coloring in all of the areas using only two colors, say A and C. The rule is that no chain with the same color that circles completely back around to the original area shall contain an odd number of areas. That includes a chain of three, where three areas touch each other, then five, seven, etc. After the map is colored in this way, we simply alternate the two colors with the other two, A then being alternated with A and B, and those with C become alternately C and D. Since the two original sets are different, and the last two alternate, then none of the same colors will ever border each other. It should be a simple thing to prove, although I have set upon doing that yet. For the last week or so, I've been concentrating on coming up with the simplest way to color in the map with the two colors to begin with, which I would then have to prove can be done every time as well, but it wouldn't be nearly as difficult as the original method.

It's a simple matter once one gets the hang of it anyway, but I'm looking for a definite method so that I can prove it always works a particular way, and so the best way I've seen to color in the areas with the original two colors so far seems to be to begin by alternating them around the outermost perimeter in a great circle and working our way inward. This automatically breaks up any potential circular chains at this point. If the outer perimeter contains an even number of areas, then the colors are all alternated. If it is uneven, then only the first and last areas will be the same, but alternating again by bringing the coloring into the next perimeter colors the third of the triple vertice differently, so no chain of three here, and we continue from there doing the same thing with the next perimeter. So one can just continue coloring this way around and around the perimeters until they reach a place where the areas start to come together toward the center. That's where I'm stuck so far, but close. Anyway, anyone that tries to four-color a triple vertice map this way by following that one rule will find it much simpler than originally using all four colors.

Dragon

2007-Apr-04, 04:07 AM

Could you please attach an illustration or two to show this?

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Apr-04, 05:28 AM

Could you please attach an illustration or two to show this?

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.Yes, of course. On the far left, I have colored the areas so that there are no odd numbered chains that come completely about. Actually, I generally just don't make any chains at all and I haven't in these. If you follow each of the two colors around, you'll see that they just kind of form stems that branch out in various ways. These all form one long adjoined stem each, but you can also have stems that are isolated, for more than one for a particular color. In the second column, I colored every other blue area with yellow. You'll notice that all of the blues and yellows become neatly separated from each other this way, so that none will border their own color. Finally, in the last column, I alternate the green with every other red in the same way. The maps are now nicely four colored.

snarkophilus

2007-Apr-04, 06:15 AM

This is a pretty nifty approach, but I don't think it will work as it stands.

Consider the simplest case where you have a looped chain: you've got a linear chain in the middle (say, ten square blocks), and two big territories around the outside (connected at the ends of the blocks). Then the big ones have to form a 2 piece loop. It simply can't be any other way, because otherwise you get something which is not a linear chain.

Now, split one of those outside ones in half.

ASCII picture of initial stage:

****************

**@@##@@##@@##**

--@@##@@##@@##--

----------------

Picture of splitting one territory:

%%%%%%%*********

%%@@##@@##@@##**

--@@##@@##@@##--

----------------

How do you draw chains in this second case?

grav

2007-Apr-04, 01:37 PM

This is a pretty nifty approach, but I don't think it will work as it stands.

Consider the simplest case where you have a looped chain: you've got a linear chain in the middle (say, ten square blocks), and two big territories around the outside (connected at the ends of the blocks). Then the big ones have to form a 2 piece loop. It simply can't be any other way, because otherwise you get something which is not a linear chain.

Now, split one of those outside ones in half.

ASCII picture of initial stage:

****************

**@@##@@##@@##**

--@@##@@##@@##--

----------------

Picture of splitting one territory:

%%%%%%%*********

%%@@##@@##@@##**

--@@##@@##@@##--

----------------

How do you draw chains in this second case?Like this.

1111111333333333

1111331111111133

3311331111111133

3333333333333333

for the original stems for one possibility (although it may be difficult to make out this way), and then

1111111333333333

1122332211221133

4422332211221144

4444444444444444

hhEb09'1

2007-Apr-04, 02:02 PM

At this point, I only wish to prove it for a map that contains only triple vertices, where three areas come together at a point, no more and no less. All of the maps that we have considered so far do this, except that the map of the US contains one point where four of the states come together. With this type of map, only one rule is necessary with the method I will use.I'm pretty sure that that assumption is sufficient.

In other words, if you can do it for those maps, you can do it for all maps. Here's a sketch of the proof: say you're starting with a map that has more than three areas come together at a point (like CO/UT/AZ/NM in the USA). Simply take the point where they come together and add a small area at that point. By expanding the point, you end up with four new intersections and one new area, but all four intersections have just three areas coming together. Do that for every such point, and you have the kind of map that you are assuming--so, then, after you color the modified map using your assumptions/method, just shrink the inserted areas back down. No new connections will be established by the shrinking, so you won't need to change/add colors. And you will have four-colored the original map.

Dragon

2007-Apr-04, 11:29 PM

I'm pretty sure that that assumption is sufficient.

In other words, if you can do it for those maps, you can do it for all maps. Here's a sketch of the proof: say you're starting with a map that has more than three areas come together at a point (like CO/UT/AZ/NM in the USA). Simply take the point where they come together and add a small area at that point. By expanding the point, you end up with four new intersections and one new area, but all four intersections have just three areas coming together. Do that for every such point, and you have the kind of map that you are assuming--so, then, after you color the modified map using your assumptions/method, just shrink the inserted areas back down. No new connections will be established by the shrinking, so you won't need to change/add colors. And you will have four-colored the original map.

--Wow, that's almost exactly how Alfred Kempe tried to take care of his exceptions. Even all the methodology and everything is the same. Have you been reading his proof?[/FONT]

--:whistle:

--lol

[font=fixedsys]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

Dragon

2007-Apr-04, 11:46 PM

Sorry that my responses with counterproofs are so generic: the last three I posted I got off the paper that dealt with different ways to disprove different attempts of Alfred Kempe, but anyways, I guess if a generic one works, I need not think to come up with a counterproof. But anyways, I know this next graph is VERY easy to colour, but I am not sure how your method would work in it.[/FONT]

As a side note, I think it is a compliment that the more we wait, the more and more your proof starts resembling his proof. Who knows, perhaps one day if you keep following his path, your creativity will lead you on a road different from the one which led him astray to a contradiction in his proof, a one which would get you a proof different from mine. I left this path a long time ago. By the way, assuming you haven't already, I recommend you don't read his proof lest once you get to the point which he missed you would not know it is the erroneous point and rather than enduring searching for a path, miss the mistake and keep following his aberration. Good luck.

By the way, July when I will be able to publish my proof is approaching![font=fixedsys]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

snarkophilus

2007-Apr-05, 07:52 AM

Good point. I originally drew it with more pieces in the middle, so it was harder to see the way to draw it, but I managed to generalize what you did to make it work out.

I am one short proof away from convinced that you've got a solution for the restricted case. :) I'll need to brush up on my graph theory if I want to try to work it out. Anyway, it's a pretty elegant method, if it works!

grav

2007-Apr-05, 12:29 PM

Good point. I originally drew it with more pieces in the middle, so it was harder to see the way to draw it, but I managed to generalize what you did to make it work out.

I am one short proof away from convinced that you've got a solution for the restricted case. :) I'll need to brush up on my graph theory if I want to try to work it out. Anyway, it's a pretty elegant method, if it works!Thanks. I think I'm close too. As far as I can figure, all I've basically got to do now is to prove that any map can be two-colored without a violation of the one rule and I've got a proof.

Dragon

2007-Apr-06, 05:18 AM

--O. M. Word. Sorry! I forgot to post the graph! And here I was, commenting on it and stuff, and alas, the graph was none.[/FONT]

--:clap:

--:wall: But here it is.[font=fixedsys]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

snarkophilus

2007-Apr-06, 05:59 AM

Make the top left and the adjacent inner one part of chain 1. Make the right hand one and the bottom left one part of chain 2. Make a new chain (of length 1) the same colour as chain 1 for the other inner piece.

grav

2007-Apr-06, 01:09 PM

Make the top left and the adjacent inner one part of chain 1. Make the right hand one and the bottom left one part of chain 2. Make a new chain (of length 1) the same colour as chain 1 for the other inner piece.Yep, that's it :), or the two outer ones on the left chain 1 and the outer one on the right chain 2, and it won't matter about the inner ones. Actually, the only ways this can't be done is where all three outer areas are the same color, of course, since that makes a chain of three, and otherwise just where an inner area is the same as the two adjoining outer ones, since they also border themselves, also forming a chain of three. Besides that, anything goes, although there are only so many possibilities for five areas anyway.

Dragon

2007-Apr-06, 03:55 PM

Sorry, I had the notion that you couldn't have more than one set of chains, one with colours 1 and 2 and the other with 3 and 4. Well, if this is down, all you have to do now is to come up with a formula that would always generate the chains, and you have a proof.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

hhEb09'1

2007-Apr-06, 06:06 PM

Have you been reading his proof?

No, just reading the thread. But I saw some of the literature about the problem thirty and forty years ago, and I worked through some topology proofs in graduate school topology and algebraic topology.

I am one short proof away from convinced that you've got a solution for the restricted case. :) What is the restricted case? I mean, what are the restrictions, again, exactly? :)

Thanks. I think I'm close too. As far as I can figure, all I've basically got to do now is to prove that any map can be two-colored without a violation of the one rule and I've got a proof."Any map can be two-colored?" I've lost the context/intent of that comment somehow, over the weeks. Obviously, we have simple maps that can't be three-colored, so I've lost the meaning of that. Can you repeat it?

snarkophilus

2007-Apr-06, 06:19 PM

The restriction is that exactly three regions must come together at any given point. It reduces the problem to that of a graph consisting entirely of (warped) triangles. Find linear chains of vertices (this is what he means by two-colouring the graph) so that there are no loops of odd length (I think a better restriction is to two-colour it so that there are no loops, period), then alternate colours within each of those partitions.

hhEb09'1

2007-Apr-06, 06:49 PM

The restriction is that exactly three regions must come together at any given point.You mean, "no more than three" right? :)

It reduces the problem to that of a graph consisting entirely of (warped) triangles.As I pointed out in my previous post, that is not really a restriction--since if there are points where more than three regions come together, you can make a map with more countries that allows you to color the original.

Find linear chains of vertices (this is what he means by two-colouring the graph) so that there are no loops of odd length (I think a better restriction is to two-colour it so that there are no loops, period), then alternate colours within each of those partitions.What does that mean, in the context of a map of of four regions, three surrounding the interior one?

Dragon

2007-Apr-06, 11:43 PM

... I worked through some topology proofs in graduate school topology and algebraic topology.

...

That would do it. :) Glad to have someone in the conversation who can explain what he means concisely. But I don't really mind when I have plenty of spare time to try to interpret their ideas. Guess it gives good practice.[/FONT]

But actually, I meant to imply I knew you really weren't reading his proof when I posted that mock conversation.

P.S. I will be going on vacation for my spring break, where I will likely have no access to a computer, so I cannot help along in the conversation for the next week or so.[font=fixedsys]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Apr-07, 12:30 AM

The restriction is that exactly three regions must come together at any given point.

You mean, "no more than three" right? :)Actually, it means three edges for the borders stem from each point, since those on the outermost perimeter would require only two regions, but you know what? I think you may have just given me a hint toward a method for this. If we count the "outside" of the map as a region, which we could do by simply circling the whole thing, since this new map would be just as legitimate, then if we were to two-color it beginning with that outermost area, all stems must move inward from there if they are not to cross the entire length of the map to form a chain, and the other color would start in the center somewhere and stem outward.

It reduces the problem to that of a graph consisting entirely of (warped) triangles.

As I pointed out in my previous post, that is not really a restriction--since if there are points where more than three regions come together, you can make a map with more countries that allows you to color the original.Well, again, it's not really triangles, since more than three of them can come together at a point, it is the edges for the borders at the vertice. But hh, how do you mean we could divide up the vertice with more than three areas by adding more areas? It would be good to know, but I don't see that. Are you thinking of the vertices here?

Find linear chains of vertices (this is what he means by two-colouring the graph) so that there are no loops of odd length (I think a better restriction is to two-colour it so that there are no loops, period), then alternate colours within each of those partitions.

What does that mean, in the context of a map of of four regions, three surrounding the interior one?It means that a line drawn through the connecting borders with the same color cannot loop back around to the original area, at least not with an odd number of areas forming the chain. Following this one rule, turning any two-colored map into a four-colored one is a cinch. It basically reduces the complexity greatly, so now I just need a proof of the new two-color theorem instead, that any map can be two-colored without the necessity of violating this one rule in order to do so. I'm thinking that if we take any map that is already four-colored, and divided those four colors into two sets of two colors, they would form the same chains as those for the two-color map to begin with. So whenever we get stuck while four-coloring and have to backtrack, it is probably just because we have unknowingly violated the one rule for two-coloring somewhere along the line. We would have to violate it for all three possible ways the sets can be divided up, though, so randomly four-coloring a map might start off easily enough, but eventually we would run into trouble if we didn't know what we were supposed to be looking out for, which is just that one rule.

snarkophilus

2007-Apr-07, 12:56 AM

You mean, "no more than three" right? :)

I meant "exactly three," but... yeah.... :)

As I pointed out in my previous post, that is not really a restriction--since if there are points where more than three regions come together, you can make a map with more countries that allows you to color the original.

I know you said it, but I skimmed it late at night, didn't really grok it, and subsequently forgot about it. Too much thinking. You are right, of course. That bodes ill for a proof of grav's method (though I still think it ought to work in some sense, because I know already that the FCT is true -- but that doesn't mean we'll ever find the conditions here to make it work).

Anyway, I just thought it was a neat approach to the problem, because it adds some structure to it, which is always a good thing.

What does that mean, in the context of a map of of four regions, three surrounding the interior one?

It means you need to draw two chains: one contains two of the outside regions, and the other contains the inside region and the remaining outside region. That's "two-colouring." Then, recolour each of those chains with alternating colours.

grav

2007-Apr-07, 01:20 AM

I know you said it, but I skimmed it late at night, didn't really grok it, and subsequently forgot about it. Too much thinking. You are right, of course. That bodes ill for a proof of grav's method (though I still think it ought to work in some sense, because I know already that the FCT is true -- but that doesn't mean we'll ever find the conditions here to make it work).That bodes ill? :think: I would have thought it would help to extend it from the restricted case to all cases, if it works out. But then, I'm not sure if I understand what hh is saying correctly, though, because I can't imagine how that can be done.

It means you need to draw two chains: one contains two of the outside regions, and the other contains the inside region and the remaining outside region. That's "two-colouring." Then, recolour each of those chains with alternating colours.Thanks. I don't think I read his question correctly there. I'm glad you understand it so well and can help to explain. :)

Dragon

2007-Apr-07, 04:16 AM

This is what he meant by adding a new area (see bmp).

Since the new graph can be coloured according to his rule, the new area can be removed after colouring, giving us a good graph because everything that touched each other still touches each other.

hhEb09'1

2007-Apr-07, 11:19 AM

I meant "exactly three," but... yeah.... :)Then, I guess, "a point" must mean "a place where more than two borders intersect"? Otherwise, using the usual concept of point, you could have have points all along the borders, and that would mean less than three. :)

But hh, how do you mean we could divide up the vertice with more than three areas by adding more areas? It would be good to know, but I don't see that. Are you thinking of the vertices here? Using Dragon's diagram, I've added labels to the areas:

http://mensware.us/fourvert.gif

The lefthand map has four areas, ABCD, but all four come together at a point. By growing area E at that point (the righthand map) we end up with a map with one more area, but each of the four intersection points have only three countries coming together. After you four-color the righthand map, just "throw away" area E--the lefthand map will still be four-colored.

If you can four-color a map where every intersection has no more than three areas coming together, then that proves that you can four-color any map.

grav

2007-Apr-07, 12:01 PM

Then, I guess, "a point" must mean "a place where more than two borders intersect"? Otherwise, using the usual concept of point, you could have have points all along the borders, and that would mean less than three. :)Using Dragon's diagram, I've added labels to the areas:

http://mensware.us/fourvert.gif

The lefthand map has four areas, ABCD, but all four come together at a point. By growing area E at that point (the righthand map) we end up with a map with one more area, but each of the four intersection points have only three countries coming together. After you four-color the righthand map, just "throw away" area E--the lefthand map will still be four-colored.

If you can four-color a map where every intersection has no more than three areas coming together, then that proves that you can four-color any map.Thank you very, very much, hh (and Dragon), for that. It's just wonderful how that works out, apparently regardless of how many borders intersect, it still becomes three with that one extra area added in at the intersection, and can then be taken away with no problem. It's just what I needed. With that one addition, it looks like I might be well on my way to a complete proof after all. :) :)

Dragon

2007-Apr-15, 05:35 PM

So, grav, have you come up with a formula to generate the chains yet?

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Apr-15, 05:57 PM

So, grav, have you come up with a formula to generate the chains yet?

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.Not yet, but I'll keep working on it. As a matter of fact, I'll start right now. :)

Dragon

2007-Apr-15, 06:36 PM

OK, so long as you still remember. In reality, if you're allowed to have more than one set of chains, then any four-coloured map, however coloured, can be split into chains of two colours, so that alone does not prove much. Good luck getting it done.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Apr-15, 06:40 PM

I guess since there are now only two possibilities for coloring each area and only one rule, the simplest method would be to just color any which way we wish, but eliminating the color that would violate the one rule for any particular area as we come across them, leaving only one possibility for that area, as we did before with the four-color map, but that still wouldn't prove that any and all possible maps can be colored this way.

Dragon

2007-Apr-15, 09:00 PM

No, my question is, what algorithm would allow you to decide:http://www.bautforum.com/attachment.php?attachmentid=5206&d=1176671166 and not lay the chains some way which does not work?

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Apr-15, 10:04 PM

No, my question is, what algorithm would allow you to decide:http://www.bautforum.com/attachment.php?attachmentid=5206&d=1176671166 and not lay the chains some way which does not work?

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.Yes, that's what I mean. All of the areas originally contain two possibilities and it does not matter which area we start with or which color we choose, since one is just as good as the other to begin with. From there, any color for an area that would violate the rule is then marked off, leaving only one choice available, so that it must be. After that is done for each run, another area must be chosen to pick a color for, so that is the tricky part. I would say it can be done almost arbitrarily, or similar to what we did before when four-coloring, but I'm not quite sure yet, so I'm still experimenting with it, and I'll still have to prove it afterward.

Dragon

2007-Apr-15, 11:35 PM

OK, you still don't get what I'm trying to say. How would you decide that it's http://www.bautforum.com/attachment.php?attachmentid=5206&d=1176671166 and not http://www.bautforum.com/attachment.php?attachmentid=5208&d=1176680132 (which does not work)? Do you have an algorithm for that?[/font]

By the way, hhEb09'1, how did you get your image to appear as an image in your post? I've been trying and trying, dragging an image into the box, changing extensions and all, et cetera, and I cannot get it to do that: all mine show up as links.[font=fixedsys]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

grav

2007-Apr-16, 02:09 AM

OK, you still don't get what I'm trying to say. How would you decide that it's http://www.bautforum.com/attachment.php?attachmentid=5206&d=1176671166 and not http://www.bautforum.com/attachment.php?attachmentid=5208&d=1176680132 (which does not work)? Do you have an algorithm for that?[/font]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.Well, if the chain numbers for the areas are chosen one at a time, then once two of the areas on the bottom are numbered, the third could not be that chain number, since that would form a loop of three, so it must be the other. It is not a very efficient algorithm yet, though, just the best I have so far. It's still just basically choosing randomly and eliminating possibilities as we go, so if it can't be one, it must be the other.

hhEb09'1

2007-Apr-16, 04:33 AM

By the way, hhEb09'1, how did you get your image to appear as an image in your post? I've been trying and trying, dragging an image into the box, changing extensions and all, et cetera, and I cannot get it to do that: all mine show up as linksIn that post, I used the IMG vB code--hit the quote button for it, and you'll see the format.

My signature to identify my posts until I find a small enough avatar.[/FONT]We gave you two of them! :)

Dragon

2007-Apr-16, 05:05 AM

Yeah, I tried that before I posted initially, and sorry, it looks just like quoting the image. I attach a screenshot of the window.[/font]

Also, I changed my signature a bit, as you can see below.[font=fixedsys]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar THAT I LIKE.

hhEb09'1

2007-Apr-16, 05:19 AM

Yeah, I tried that before I posted initially, and sorry, it looks just like quoting the image.When you post a reply to the thread, scrool way down to the bottom of the page. Off to the left will be a couple links, one to a vB code page (http://www.bautforum.com/misc.php?do=bbcode), and the other to an explanation of the IMG tag (http://www.bautforum.com/misc.php?do=bbcode#imgcode). Well, there's more, but that should do it. :)

HenrikOlsen

2007-Apr-16, 06:58 AM

I've been trying and trying, dragging an image into the box, changing extensions and all, et cetera, and I cannot get it to do that: all mine show up as links.

Changing the extension doesn't change the content, so even if you change the filename extension to .png or .gif it's still a BMP file, and as such won't get a thumbnail image when put in as an attachment.

For that to work, you need a program that can actually save in one of the supported formats.

I tend to promote The GIMP (http://www.gimp.org/) at this point, since it's free and is available for any OS you're likely to be using(*NIX, Windows and OSX) and does everything I've needed from an image manipulation program.

Dragon

2007-Apr-16, 11:14 PM

Actually, if you just change the extension, the website does not even allow the file to be uploaded. Therefore, I have to actually save it as a different type of file to display it as a different filetype here.[/font]

On the other hand, grav, thank you very much for your advice: I learned many new things. However, I did not learn much about the [IMG] tag (see, I know now how to keep it from trying to convert that tag into an image). I had done in the past exactly what the instructions outlined. So I'm still going along with the filetype case. Apparently, gif works with the [IMG] tag, but gif loses quality. So which other images work for the tag without losing quality?[FONT=fixedsys]

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

hhEb09'1

2007-Apr-17, 01:02 AM

Apparently, gif works with the [IMG] tag, but gif loses quality. What do you mean by that? GIF is a lossless compression, isn't it?

Dragon

2007-Apr-17, 01:32 AM

Remember, we went through this? Well, just in case, this post is where I demonstrated the loss of quality.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar.

snarkophilus

2007-Apr-17, 03:32 AM

GIF only loses quality if you have more than 256 colours AND you are using a standard colour palette. When you save your picture, use the option to have a customized palette, and it will be fine.

hhEb09'1

2007-Apr-17, 03:52 AM

GIF only loses quality if you have more than 256 colours AND you are using a standard colour palette. When you save your picture, use the option to have a customized palette, and it will be fine.Here is a copy of Dragon's PNG file, saved as a GIF:

http://mensware.us/dragons.gif

Dragon

2007-Apr-17, 04:41 AM

Well, first of all, the image that I posted here way back was saved as a GIF with only 16 colours and a custom palette, and so it still did not work. And my computer classifies hhEb09'1's picture as a 256-colours BMP image. Really odd, because were that true, it would show up as a link. So I investigated the case if that is not true. I open his image, click "Save As GIF", and it does not change. I open my image, do the same thing, and it doesn't. I save his file as 16-colour, then PNG, and JPG, and it still works. I open a new file of mine, and it doesn't. I try different ways of saving with my file, and it does not help. I try modifying your file to see if there's something magical about it; as long as I only pour colours, it works. But add something else, and voila.

═════════════════════════════════════════════════╣ ╠═══════════════════════════

My signature to identify my posts until I find a small enough avatar that I really like.

peter eldergill

2007-Sep-03, 03:33 AM

*Bump*

I recall that Dragon was supposed to have a "proof" of the theorem published by July....

Does anyone else recall that?

Pete

hhEb09'1

2007-Sep-03, 11:54 AM

I recall that Dragon was supposed to have a "proof" of the theorem published by July....

Does anyone else recall that?He mentioned it last in this post (http://www.bautforum.com/general-science/29705-four-color-theorem-12.html#post962628), but I'm not sure he said where it would be published. He hasn't post to BAUT since his last post to this thread.

grav, how's your proof going?

hhEb09'1

2008-Feb-20, 01:23 AM

I was just reading Courant and Robbins and thought this'd be a good place to display that proof of the five-color theorem, since I don't remember doing it before. They go about it in a roundabout way, but here's the essentials.

Any map can be drawn on a sphere (just take the outside region that surrounds the whole map and shrink its border to a point--a coloring of the 2D map will color the spherical one, and vice versa). Applying the algorithm that I mentioned earlier (http://www.bautforum.com/general-science/29705-four-color-theorem-12.html#post963950), results in a polyhedron where 3 edges meet at each vertex (this is called regular), but each edge is shared by two vertices, so the number of edges E is 3/2 times the number of vertices V (in other words, 3V-2E=0). If all the faces have six or more edges then E is greater than 6 times F divided by 2 (in other words, 3F-E<=0), or

0 >= 3F - E

0 >= 3F - E + (3V - 2E)

0 >= 3F - 3E + 3V

0 >= F - E + V

But that contradicts Euler's famous relationship 2 = F - E + V, so we know that at least one region of a regular map must have less than six other regions touching it. (I ran across this part of the proof years ago in D'Arcy Thompson's On Growth and Form. Applied to the illustration (http://home.hetnet.nl/~turing/aulonia_1.jpg) (webpage (http://home.hetnet.nl/~turing/anaxonia.html)) of the radiolarian Aulonia hexagona Hkl., it says that there must be a pentagon or two mixed up in all those hexagons!)

Take one of the regions, R, that has five or less other regions touching it. If two of the surrounding regions do not touch each other (this must be so, for four or five), remove the associated edges, otherwise just remove one edge. This results in a regular map that has either 1 or 2 less regions. If that smaller (fewer regions) map can be colored with five colors, then so can the larger, just by adding back in the boundaries, and coloring R with whatever color does not touch it. So, we can reduce the size of the map until we only have to use five colors, then we can add back the edges until the original map is five-colored.

Obviously, the proof of the four-color theorem is a long ways from this simple proof!

PS: over two years ago, peter eldergill (http://www.bautforum.com/general-science/29705-four-color-theorem-4.html#post568906) and Grey (http://www.bautforum.com/general-science/29705-four-color-theorem-4.html#post569036) linked to webpages that had explanations of the above proof.

grav

2008-Feb-23, 01:29 AM

I was just reading Courant and Robbins and thought this'd be a good place to display that proof of the five-color theorem, since I don't remember doing it before. They go about it in a roundabout way, but here's the essentials.

Any map can be drawn on a sphere (just take the outside region that surrounds the whole map and shrink its border to a point--a coloring of the 2D map will color the spherical one, and vice versa). Applying the algorithm that I mentioned earlier (http://www.bautforum.com/general-science/29705-four-color-theorem-12.html#post963950), results in a polyhedron where 3 edges meet at each vertex (this is called regular), but each edge is shared by two vertices, so the number of edges E is 3/2 times the number of vertices V (in other words, 3V-2E=0). If all the faces have six or more edges then E is greater than 6 times F divided by 2 (in other words, 3F-E<=0), or

0 >= 3F - E

0 >= 3F - E + (3V - 2E)

0 >= 3F - 3E + 3V

0 >= F - E + V

But that contradicts Euler's famous relationship 2 = F - E + V, so we know that at least one region of a regular map must have less than six other regions touching it. (I ran across this part of the proof years ago in D'Arcy Thompson's On Growth and Form. Applied to the illustration (http://home.hetnet.nl/~turing/aulonia_1.jpg) (webpage (http://home.hetnet.nl/~turing/anaxonia.html)) of the radiolarian Aulonia hexagona Hkl., it says that there must be a pentagon or two mixed up in all those hexagons!)

Take one of the regions, R, that has five or less other regions touching it. If two of the surrounding regions do not touch each other (this must be so, for four or five), remove the associated edges, otherwise just remove one edge. This results in a regular map that has either 1 or 2 less regions. If that smaller (fewer regions) map can be colored with five colors, then so can the larger, just by adding back in the boundaries, and coloring R with whatever color does not touch it. So, we can reduce the size of the map until we only have to use five colors, then we can add back the edges until the original map is five-colored.

Obviously, the proof of the four-color theorem is a long ways from this simple proof!

PS: over two years ago, peter eldergill (http://www.bautforum.com/general-science/29705-four-color-theorem-4.html#post568906) and Grey (http://www.bautforum.com/general-science/29705-four-color-theorem-4.html#post569036) linked to webpages that had explanations of the above proof.That's interesting. I would have to look it over some more to get the full jest of it, though. Euler's relationship is fascinating to me. It's one of the first things that got me thinking in three dimensions. I never thought about starting with a two dimensional map and wrapping that around, though, making each area a face. It's easier for me to think about if I don't wrap the border around to a point, though, but another face, which would be the outside of the map originally, then, although the point can be opened up anyway, using the algorithm you provided earlier in the thread. The way you stated that with the spherical map, I can now see how Euler's relationship can be shown to be true with what you were describing.

If we start with a single area and build up from that, such as a hexagon, then the border will have an equal number of vertices and edges, and two faces, inside and outside of the shape, since the outside can be wrapped around into another face in the manner you described above. This provides us with the relationship 2 = F - E + V, although kind of after the fact, since we really just have F=2 and E=V, but we can still show thereon that the relationship holds regardless. We can then add another face that connects to the original one, brought out from any two of the vertices of the original face, with any number of vertices and edges of its own, always gaining one more edge than vertices in the process, plus one extra face, so the relationship stays the same. If we continue to add faces this way, the same thing will occur each time, so the relationship remains constant throughout the process. Also, if we use the algorithm you demonstrated earlier in the thread to make the map regular, then we add one face, along with an equal number of edges and vertices, but subtract the original vertice, so the relationship stays the same. It therefore works out for vertices with any number of edges stemming from them.

hhEb09'1

2008-Feb-23, 03:10 PM

Since any polyhedron has a vertex with at least three edges radiating from it (other wise, it would be just a ring, wouldn't it?), you can subtract faces, edges, vertices, until you arrive at a tetrahedron. It's easy to show that Euler's formula works for a tetrahedron, and then your approach shows that it works for the original too.

The last step, going from five color theorem to four color theorem, took a long time! :)

grav

2008-Feb-24, 01:04 AM

Since any polyhedron has a vertex with at least three edges radiating from it (other wise, it would be just a ring, wouldn't it?), you can subtract faces, edges, vertices, until you arrive at a tetrahedron. It's easy to show that Euler's formula works for a tetrahedron, and then your approach shows that it works for the original too.

The last step, going from five color theorem to four color theorem, took a long time! :)Oh, so that would be the proof for the four color theorem right there, then! Is that what you mean? If we can start with any polyhedron and reduce it to a tetrahedron by subtracting faces, then we should be able to start with a tetrahedron and add faces to produce any polyhedron. So we have four faces on the tetrahedron originally, each with a different color since they are all joined, which would also show one needs at least four colors to begin with. Then we open up any vertice to create another face. The vertice will join three faces, each necessarily with a different color, so we use the fourth color for the new face each time. If we just keep opening up new faces in the same positions relative to the others in the original map we are trying to color, after it is made regular, plus one face that will act as the outside beyond the border once the polyhedron is unwrapped, then we should be able to reproduce any regular map, already four-colored, in this way, shouldn't we? After unwrapping the polyhedron, we would have the map we made regular, and then we would just make it irregular again by subtracting areas until we regain the original map, already four-colored. Does that sound like it might work out to you?

KaiYeves

2008-Feb-24, 01:49 AM

Darn, I thought this was a thread about comic books!

hhEb09'1

2008-Feb-24, 10:42 AM

Comic books have theorems now? Whoa, I guess I gotta get back into them

grav

2008-Feb-24, 02:21 PM

Oh, so that would be the proof for the four color theorem right there, then! Is that what you mean? If we can start with any polyhedron and reduce it to a tetrahedron by subtracting faces, then we should be able to start with a tetrahedron and add faces to produce any polyhedron. So we have four faces on the tetrahedron originally, each with a different color since they are all joined, which would also show one needs at least four colors to begin with. Then we open up any vertice to create another face. The vertice will join three faces, each necessarily with a different color, so we use the fourth color for the new face each time. If we just keep opening up new faces in the same positions relative to the others in the original map we are trying to color, after it is made regular, plus one face that will act as the outside beyond the border once the polyhedron is unwrapped, then we should be able to reproduce any regular map, already four-colored, in this way, shouldn't we? After unwrapping the polyhedron, we would have the map we made regular, and then we would just make it irregular again by subtracting areas until we regain the original map, already four-colored. Does that sound like it might work out to you?Actually, what I described above is too simple. It would just produce a bunch of triangular areas. We would also have to open up some of the edges from one of the vertices, splitting the original edge, and producing an extra edge for one of the areas, along with creating another face and vertice, though. We could also stretch vertices out into another edge and vertice as well, creating a border between two of the original faces, and an extra edge each. That sort of thing. But those might affect the four coloring, I'm not sure.

Basically, though, I'm thinking that if we can make the original map regular, then twist it around into a polyhedron, and reduce that to a tetrahedron by subtracting faces, then whatever precise method we used to do that can then be exactly reversed, four-coloring each face as we add them back in. In fact, now that I think about it some more as I'm writing this, we could probably by-step the 3D part of that altogether, and might not need to make it regular either, actually, but just reduce the original map by subtracting faces until we get three adjoining areas and the outside of the border, which would represent the same thing as the tetrahedron anyway, and then just build that back up again, four-coloring as we go, right? But that might be different than that algorithm you mentioned after all, however, since adding faces to make it regular and subtracting the same ones again without affecting the four-coloring is not the same as subtracting areas and then adding them back in. No more than three colors could meet at any vertice as we build it back up so we can give the fourth color to the new face each time.

grav

2008-Feb-24, 02:57 PM

Since we cannot subtract and then add areas back in the same way according to that algorithm for making maps regular, I'm not sure about getting the method I described above to work out, but it gave me an idea. I can still use the algorithm for that two-color method I came up with earlier in the thread. It's a simple matter to show that if we can two-color a map in that way, it can be four colored. The only problem was coming up with a method to two-color it to begin with. Well, I'm thinking that once the map is made regular, we don't need to stop there. We can keep adding areas by opening up the triple vertices at will. So maybe we could just two-color the map with a simple spiral or something. If we get to an area that thwarts us somehow, we can just open up an extra area to keep us on track. Then, after the map has been two-colored and then four-colored, we can close those extra areas, along with the ones we added to make the map regular.

hhEb09'1

2008-Feb-24, 07:47 PM

Then, after the map has been two-colored You know it is impossible to two color some maps?

Maybe I need to go back over some old posts to see what you mean here.

KaiYeves

2008-Feb-24, 08:55 PM

Comic books have theorems now? Whoa, I guess I gotta get back into them.

Some may. But comic book-realted stuff is often described as "four colour".

grav

2008-Feb-24, 10:56 PM

You know it is impossible to two color some maps?

Maybe I need to go back over some old posts to see what you mean here.It starts with post #325 and there are some examples in post #327.

hhEb09'1

2008-Feb-24, 11:38 PM

I remember now--I was confused before! :)

It is impossible to two-color chains with an odd number of regions. If you color the last (odd) region with the third color, to start the next interior chain, you arrive at a problem when the second chain closes with an odd number. This diagram starts with the asterisk, and goes counterclockwise, with colors 1 and 2 alternating. Each change of character indicates a new region. The outside chain alternates colors 1 and 2, but must use 3 at the last. So, we can use color 4 for the x's, and 3 for the y's, but what do we color the z's? We'd need a fifth color.

2221122111*

11xxyyxx33

22xx....33

22xx....33

22yyxxzz33

1112211222

grav

2008-Feb-25, 05:09 AM

I remember now--I was confused before! :)

It is impossible to two-color chains with an odd number of regions. If you color the last (odd) region with the third color, to start the next interior chain, you arrive at a problem when the second chain closes with an odd number. This diagram starts with the asterisk, and goes counterclockwise, with colors 1 and 2 alternating. Each change of character indicates a new region. The outside chain alternates colors 1 and 2, but must use 3 at the last. So, we can use color 4 for the x's, and 3 for the y's, but what do we color the z's? We'd need a fifth color.

2221122111*

11xxyyxx33

22xx....33

22xx....33

22yyxxzz33

1112211222

Yes, that was the only condition, that we do not not use closed loops with an odd number of regions. I just try to avoid using any closed loops at all, only chains with open "stems" branching off of them. For that diagram, one option would be to color zz the same as the 2's, bringing it up from the 11 at the bottom, and running the chain in that way. Then the 3's and 222 on the right could be another chain.

hhEb09'1

2008-Feb-25, 05:16 AM

Yes, that was the only condition, that we do not not use closed loops with an odd number of regions. I just try to avoid using any closed loops at all, only chains with open "stems" branching off of them. For that diagram, one option would be to color zz the same as the 2's, bringing it up from the 11 at the bottom, and running the chain in that way. Then the 3's and 222 on the right could be another chain.I know I can color it with four colors! :)

My point is, your directions have to be specific enough that I do not get into the trouble that I illustrated. I thought I was following your directions--I was, wasn't I?

Of course you can always change your directions, but that means that your original set is flawed--and the present set may be as well. Until you prove it.

grav

2008-Feb-25, 01:33 PM

Oh, well, I don't have an algorithm for two-coloring yet; that's what I'm still working on. So far it can just be colored in any way feasible with the two colors originally, such as blue and green, with the only rule being that we don't loop the same color completely back around with an odd number of regions, like three adjoining regions, or a loop of five, seven, etc. That leaves us with chains of two colors like the examples in the first column in the image below. It doesn't have to be one long chain each either. We can have two or more separate chains for each. We can also have even numbered loops of regions, but I generally avoid loops altogether.

That simplifies it for me, turning the four color theorem into a two color one. I still have to prove that all maps can be two colored in this way. So far, though, I can only prove that once this is done with the two colors, we can simply alternate every other blue with yellow and every other green with red to produce a four-colored map.

bleuprint

2009-Apr-05, 11:07 AM

Since 2008/08/23 I put a "Blueprint for a classic proof of the four colour theorem" on

http://arXiv.org/abs/0802.1535

It is based on Hamilton circuits in fully triangulated planar graphs.

Up to now I did not get many reactions on it, so I gues it must be wrong but nobody says what exactly is wrong with it.

Please tell me

or even better if possible

correct it or use it for your own proof and let me know.

Bleuprint

hhEb09'1

2009-Apr-05, 01:59 PM

correct it or use it for your own proof and let me know.

I haven't read the paper yet, just that page with the abstract. I have two questions first, why do you call it a "blueprint," are you saying it is not actually a proof, just a suggestion of how it might be proved? That could be why you're not getting much response.

Also, what is "hocus-pocus of the trio's"? :)

ETA: welcome to BAUT!

bleuprint

2009-Apr-05, 02:46 PM

In the two previous versions on the same site I used an association of every vertex (except two) with two triangles and called it trios. It's not important in this version.

For me it's a PROOF but as I am not a mathematician I may only pretend it's a BLUEPRINT. Also because I had to rely too much on the figures to prove the key statement in Theorem 2.

Thanks anyway for the response, I start feeling less alone on the world.

Bleuprint

hhEb09'1

2009-Apr-05, 04:07 PM

Also because I had to rely too much on the figures to prove the key statement in Theorem 2.

There's a good place to start then! :)

From the paper (http://arxiv.org/ftp/arxiv/papers/0802/0802.1535.pdf), page 9:

THEOREM 2: Any triangle-vertex of a triangulated polygon has a pair of different V3#'s for each combination of the pairs in the other triangle-vertices. This difference property does not change if we add the same number mod3 to the V3#'s of one or more vertices in the set of the CV3#.Page 2:

One gets yet another scheme by giving an orientation (±1) to each triangle (Heawood 1898) so that their sum around each vertex is a multiple of 3. We call this a T2# (Triangle2-numbering). If one makes the sum mod3 of the T2#'s adjacent to a vertex one gets a 0, 1 or 2 for that vertex. We call this a V3# (Vertex3-numbering). A good combination of T2# for all the triangles results in a V3#=0 for all the vertices.Page 3:

Hereafter we often have to speak about the combinations of numberings. We do that by putting a C before the abbreviation. e.g.: a CT2# for x triangles indicates one combination of Triangle2-numberings for the set of x triangles.

bleuprint

2009-Apr-07, 07:13 AM

Blueprint3 for a Classic Proof of the 4CT (http://arXiv.org/abs/0802.1535)

The first version (v1) on the same site is in fact simpler, but one person said me that it has circular references in it.

Is it, and if so does it matter?

Trying to prove better that there are no circular references (or that it doesn't matter), version 3 was made with the disadvantage that it is more complex. But it has also the more general theorem 3 as an advantage.

In terms of vertex-coloring theorem 3 says:

Given a triangulated polygon (with or without inner vertices). There is always a proper coloring of all its vertices for which the first and the last vertex of any three successive boundary vertices can always have a different color.

In fact there is always a proper vertex-coloring for which any two boundary vertices can have a different color. Thus any edge can be added. Then a fully triangulated graph with a proper vertex-coloring can be constructed, starting with a triangulated polygon without inner vertices.

Kempe chaining cannot give the same result.

Bleuprint

To the others: Please don't let hhEb09'1 do the job alone to break down this bleuprint-proof, or he may have "to eat his hat" as he mentioned in an earlier reply (#??) in this thread.

bleuprint

2009-Apr-16, 01:10 PM

:cry:

This discussion started with #384 about this paper (http://arXiv.org/abs/0802.1535). The proof is based on the dual of "Heawood's vertex character".

Please say SOMETHING (especially about Theorem2):

Is it not well formulated, not understandable, too complex ?

or is it not convincing, not complete ?

or is it simply wrong???????

I tested Theorem4 in Excel with ALL the possible T2# for nearly all triangulated graphs up to 9 vertices (excell can't do more). No contradictions. But of coarse this is not a proof.

Blueprint

PS:On the odd days of the week I think it's correct, but on the even days I think it's wrong and in the weekends I try to forget it.

hhEb09'1

2009-Apr-16, 07:30 PM

I tested Theorem4 in Excel with ALL the possible T2# for nearly all triangulated graphs up to 9 vertices (excell can't do more). No contradictions.

Here is Theorem 4:

THEOREM 4: In a good Edge3-coloured triangulated polygon with (or without) vertices in it, the number of edges on the perimeter with the same colour has the same parity as the total number of edges on the perimeter.

3.2 3-colouring of the edges

Another scheme, called a Tait colouring, is a 3colouring of the edges so that each triangle has 3 different coloured edges (Tait 1880). We call this an E3c (Edge3-colouring).

But of coarse this is not a proof.That's what we need.

bleuprint

2009-Apr-16, 09:07 PM

Correction sorry

"I tested Theorem4 in Excel with ALL the possible T2# for nearly all triangulated graphs up to 9 vertices (excell can't do more). No contradictions. But of coarse this is not a proof."

must be

"I tested Theorem3 in .... of coarse such a test is not a proof"

(Theorem 4 is OK).

That's what we need.

A hint or a proof that Theorem3 is not proved.

.....That's what I need.

Bleuprint

hhEb09'1

2009-Apr-18, 01:08 PM

One possible source of confusion for a reader is your use of "triangulated planar graph" for "maximal planar graph". That's not an unusual usage I'm sure but then your theorems talk about triangulated polygons, which are not triangulated planar graphs.

Well, I got confused once. :)

bleuprint

2009-Apr-20, 07:22 AM

One possible source of confusion for a reader is your use of "triangulated planar graph" for "maximal planar graph". That's not an unusual usage I'm sure but then your theorems talk about triangulated polygons, which are not triangulated planar graphs.

Well, I got confused once. :)

:whistle:From the abstract:

"Such orientation is first used separately on one of the two triangulated polygons resulting from a Hamilton circuit in a triangulated planar graph with v vertices. The graph is then reconstructed by adding the triangles of the other polygon one by one. When the graph is totally reconstructed there is always a combination for the orientations of the triangles for which their sum around each of v-2 successive vertices in the Hamilton circuit is a multiple of 3."

It looks strange that two adjacent vertices are disregarded until the end of the proof, but it's essential.

Added as a teaser:

All planar triangulated graphs where the degree of all its vertices is a multiple of 3, have an even number of vertices. Prove it.

[Their vertices can be four colored using the following algorithm: 3-color the vertices of one triangle. Give the other vertex of an adjacent triangle the fourth color. Check first for a K4. Then for such triangulated graph on 8, 10 ... vertices (there exist no such graph with 6 vertices). ]Bleuprint

hhEb09'1

2009-Apr-20, 03:13 PM

Added as a teaser:

All planar triangulated graphs where the degree of all its vertices is a multiple of 3, have an even number of vertices. Prove it. By "planar triangulated graph" you mean "triangulated planar graph", right? In other words, a maximal planar graph?

bleuprint

2009-Apr-20, 03:20 PM

By "planar triangulated graph" you mean "triangulated planar graph", right? In other words, a maximal planar graph?

Yes, where ALL regions are triangles also the infinite region.

Bleuprint

hhEb09'1

2009-Apr-20, 04:34 PM

Added as a teaser:

All planar triangulated graphs where the degree of all its vertices is a multiple of 3, have an even number of vertices. Prove it.

Hmmm, wouldn't all vertices having a multiple of 3 mean that they all are 3? In which case the number of vertices is two times the number of faces, minus 4. Which is even.

bleuprint

2009-Apr-20, 05:07 PM

Hmmm, wouldn't all vertices having a multiple of 3 mean that they all are 3? In which case the number of vertices is two times the number of faces, minus 4. Which is even.

No, see below with v3=4, v6=6 and v=v3+v6=10.

And also another one with v3=5, v6=6 and v9=1 and v=v3+v6+v9=12.

Of coarse the number of odd vertices is always even (for any graph).

hhEb09'1

2009-Apr-21, 02:13 PM

Nice. I'm not sure now how I convinced myself otherwise! :)

bleuprint

2009-Apr-23, 04:25 AM

For the others this is about:

All triangulated planar graphs where the degree of all the vertices is a multiple of 3, have an even number of vertices. Prove it.

My prove is a little tricky (will be posted on sunday) and in fact I'm interested to find another one using equations like:

2*e = 3*t= 3*v3 + 6*v6 + 9*v9... with e:number of edges, t:number of triangles and vx: number of vertices with degree x

v= v3 + v6 + v9 ...

2*n= v3+v9+v15+... the total number of odd vertices is even

2*m=t the number of triangles is even

....

I tried but without success :doh:.

hhEb09'1

2009-Apr-23, 02:38 PM

I tried but without success :doh:.Let's see, for a maximal triangulated graph, if you count the "outside" triangle as a face, it is equivalent to a triangulated solid figure, so Euler's formula applies: V - E + F =2

Since it is triangulated, the number of edges E is three times the number of faces F, divided by two because each edge is shared by two faces. E = 3F/2

So, V - E/3 = 2, which means that if one of V or E is even, the other is. Also, V - F/2 = 2, which means that if V is even, then F has to be divisible by four. And if F is divisible by four, then V is even.

bleuprint

2009-Apr-24, 02:49 PM

So, V - E/3 = 2, which means that if one of V or E is even, the other is. Also, V - F/2 = 2, which means that if V is even, then F has to be divisible by four. And if F is divisible by four, then V is even.

OK if F=4*n then also E=6*n and then V-2*n=2 and V is even. But why should they?

Bleuprint

hhEb09'1

2009-Apr-24, 03:30 PM

But why should they?

Good question.

And I'll have to go back and look--how does it help prove the four-color theorem?

bleuprint

2009-Apr-24, 05:59 PM

.

And I'll have to go back and look--how does it help prove the four-color theorem?

It was added as a teaser in #393 and it helps to get the hang of it. But as this discussion is now a dialogue I think that others must have now very, VERY serious arguments to interrupt us (*). As promised I post my 'tricky" solution on this teaser on sunday. By the way dear hhEb09'1, I want your advise: should I try to repeat my proof of the 4CT step by step in this dialogue or ...? Your opinion please as a moderator, and I will try to do so.

Bleuprint

(*) To the spectators: don't worry about this, as Pythagoras (also a philosopher) said that more than the gladiators, more than the commercants, the spectators were the MOST important persons in the circus.

bleuprint

2009-Apr-26, 08:32 AM

All planar triangulated graphs where the degree of all its vertices is a multiple of 3, have an even number of vertices.

Sketch of the proof:

1) 3-color the edges around each vertex with colors "0, 1 and 2" in the same rotational direction (the edge-colors in the triangles are then in the opposite rotational direction). We have v-2 edges of each color.

2) Make a new graph by deleting all edges with color "0".

- all regions are now quadrangles, and each quadrangle has two "1" and two "2" edges.

- all vertices in this new graph have an even degree (= 2/3 of the original one), its regions can be 2-colored.

3) Color the regions of this new graph with black and white.

4) The number of edges with color "1" is equal to two times the number of black quadrangles, or 2*e"1" = v-2.

Thus the number of vertices is even.

Relation with the 4CT:

The vertices of such graphs can easily be 4-colored using the following algorithm:

- color the vertices of one triangle with three colors.

- color the 4th vertex of any adjacent triangle with the 4th color.

Such graphs are somewhat "counterparts" of MPG with all vertices even. Their vertices can be 3-colored in the following way:

- color the vertices of one triangle with three colors.

- color the 4th vertex of any adjacent triangle with the 3th color (the same color as the opposite vertex).

bleuprint

2009-May-01, 06:31 AM

Since 2008/08/23 I put a "Blueprint for a classic proof of the four colour theorem" on

http://arXiv.org/abs/0802.1535

Up to now I did not get many reactions on it, so I gues it must be wrong but nobody says what exactly is wrong with it.

Again not many reactions to the point. Why not stop this discussion.

Bleuprint

To hhEb09'1: thanks for the dialogue and below is a suggestion in case you keep your promise about your hat.

hhEb09'1

2009-May-01, 10:05 AM

To hhEb09'1: thanks for the dialogue and below is a suggestion in case you keep your promise about your hat.YW, and I kept my promise! :)

If you are thinking you'd like a similar offer, I dunno. Are you saying your attempt, as presented, is a proof, or a blueprint of a proof? I thought you'd said the latter.

grav

2009-May-02, 05:37 PM

Sketch of the proof:

1) 3-color the edges around each vertex with colors "0, 1 and 2" in the same rotational direction (the edge-colors in the triangles are then in the opposite rotational direction). We have v-2 edges of each color.

2) Make a new graph by deleting all edges with color "0".

- all regions are now quadrangles, and each quadrangle has two "1" and two "2" edges.

- all vertices in this new graph have an even degree (= 2/3 of the original one), its regions can be 2-colored.

3) Color the regions of this new graph with black and white.

4) The number of edges with color "1" is equal to two times the number of black quadrangles, or 2*e"1" = v-2.

Thus the number of vertices is even.

Relation with the 4CT:

The vertices of such graphs can easily be 4-colored using the following algorithm:

- color the vertices of one triangle with three colors.

- color the 4th vertex of any adjacent triangle with the 4th color.

Such graphs are somewhat "counterparts" of MPG with all vertices even. Their vertices can be 3-colored in the following way:

- color the vertices of one triangle with three colors.

- color the 4th vertex of any adjacent triangle with the 3th color (the same color as the opposite vertex).This doesn't look like a proof to me, just some sort of algorithm that still needs to be proved. I can't visualize how one would make an "All planar triangulated graphs where the degree of all its vertices is a multiple of 3" anyway, except to the first degree where a single large triangle is incribed with three smaller ones that meet in the middle, giving four 3-vertices, although I haven't tried to work any others out on paper. After that, though, one cannot add any more triangles with all 3-vertices that I can see offhand, but one can open up the vertices that already exist by placing triangles in place of the vertices themselves, but that would make irregular rectangles out of the adjacent areas instead of triangles, while keeping all 3-vertices for the map, however. Each time this is done, it will turn a single 3-vertice into 3 3-vertices and three more edges, so increasing the number of vertices by two each time. Starting with four 3-vertices and increasing by two 3-vertices each time one is opened will keep the total number of 3-vertices even as you say, yes.

grav

2009-May-02, 05:46 PM

All planar triangulated graphs where the degree of all its vertices is a multiple of 3Oh, I just realized you said the vertices are a multiple of 3. I knew that before when I saw it, but had forgotten, I guess. Anyway, I'll leave that last post so you know somebody else is reading your posts too :), although I've read through your paper a couple of times and still don't get what you're saying with that, but I'll continue thinking about your teaser.

grav

2009-May-02, 11:41 PM

All planar triangulated graphs where the degree of all its vertices is a multiple of 3, have an even number of vertices. Prove it.Sorry, bleuprint. Your theorem doesn't work. Below is an image of a simple triangular graph with six 3-vertices and one 6-vertice. You were close, though, but the 6-vertice messed you up. The theorem should read "All planar triangulated graphs where the degree of all its vertices is odd, have an even number of vertices". The reason is that every edge lies between two vertices, so if we add all of the leading edges coming off of each of the vertices together (the degrees), we must then always be able to divide that by two. So if all of the vertices are odd, then there must be an even number of vertices in order to be able to do that, regardless of whatever combination of odd vertices there might be. Any even numbered sets of odd vertices can already be divided by two, and the remaining odd sets of odd vertices must add together to produce an overall even number also.

grav

2009-May-03, 12:52 AM

Just in case the graph itself should have been triangular, whereas mine is square, below is another graph where I have brought in the two upper corners to make a triangle, but the vertices will remain the same nonetheless.

Also, I have come to realize that regardless of the shape of the graph, the shape of any of the areas within the graph, or the total number and degree of the vertices, the number of all of the odd degree vertices must still be even. Since the addition of all of the degrees of all of the vertices must be divisible by two, regardless of any of the shapes of the areas, the even degree ones already will be, so there must still be an even number of odd degree vertices in any graph as well.

hhEb09'1

2009-May-03, 01:42 AM

Just in case the graph itself should have been triangular, whereas mine is square, below is another graph where I have brought in the two upper corners to make a triangle, but the vertices will remain the same nonetheless.Nice try, but the outside must be a triangle too, only three sides.

grav

2009-May-03, 01:42 AM

Thinking about it further, the same logic can also be applied to the areas. Each area must share an edge with another area, considering the outer infinite region to be an area also, with its edges lying between all vertices on the perimeter, equal to the number of vertices that coincide with the perimeter. So the sum of all of the edges of each of the areas must be even, in order to be divided by two to gain the actual number of edges present in the graph. The sum of all of the even edged areas is already even, so there must be an even number of odd edged areas in any graph, including the outer region if it also has an odd number of edges that lie on the perimeter.

grav

2009-May-03, 01:46 AM

Nice try, but the outside must be a triangle too, only three sides.I'm not sure what you mean, Hh. :eh: :) I left part of the original graph to show what I did, but here is another image without it.

grav

2009-May-03, 02:43 AM

Okay, I think I see what you mean. Looking at bleuprint's images in post #397, it looks like all of the triangulated areas have only three vertices each. My outer triangle has six, so that would actually constitute six edges, I suppose. So even straight line edges with a vertice upon it counts as two edges. That would also go for what I was saying about the odd edged areas in post #412, I've realized, so they would really be areas with an odd number of vertices instead of edges to make things easier in regards to that post. I will see if I can construct a truly triangular graph containing an odd number of vertices with degrees of a multiple of three, then.

hhEb09'1

2009-May-03, 03:33 AM

Okay, I think I see what you mean. Looking at bleuprint's images in post #397, it looks like all of the triangulated areas have only three vertices each. My outer triangle has six, so that would actually constitute six edges, I suppose. So even straight line edges with a vertice upon it counts as two edges. Right. The entire graph must be completely triangulated, which means that if two vertices can be connected by an edge without crossing another edge, they are.

grav

2009-May-03, 04:08 AM

Right. The entire graph must be completely triangulated, which means that if two vertices can be connected by an edge without crossing another edge, they are.Okay, thanks Hh. Under those conditions, then, the theorem obviously hasn't been disproven. Has it been proved yet?

Well, I haven't been able to constuct a graph that disproves it yet either, but it gets very tedious doing it that way, so I will have to try to work through the math. So far all I can do is refer to post #412, where the number of areas with an odd number of edges, and therefore vertices, must be even. Since the entire graph must be composed of areas with three edges each, then the total number of areas in the graph, including the outer region, must always be even. I'm trying to work from there.

hhEb09'1

2009-May-03, 10:20 AM

So far all I can do is refer to post #412, where the number of areas with an odd number of edges, and therefore vertices, must be even. Since the entire graph must be composed of areas with three edges each, then the total number of areas in the graph, including the outer region, must always be even. I'm trying to work from there.Refer to post #400. If the number of faces (areas) is divisible by four, then the number of vertices is even.

grav

2009-May-03, 05:08 PM

Refer to post #400. If the number of faces (areas) is divisible by four, then the number of vertices is even.Ah, yes. I saw that before but it flew completely over my head at the time. Now that I've worked with it some on my own, though, I suddenly understand it perfectly. Funny how that works. Anyway, I've got a little bit, not much.

Okay, so far you've determined that V - E + F = 2 and 3F / 2 = E, giving V - F / 2 = 2. I see how that works out. Also, since all of the faces must have three vertices each, then the sum of the degrees of all of the vertices will equal three times the number of faces, so S / 3 = F, and we get V - S / 6 = 2. Now, if all of the vertices were 3-vertices, so that S = 3 V, we find that V - S / 6 = V - (3 V) / 6 = 2, whereas V = 4 then, so there is only one solution for that. If all of the vertices are 3-vertices, there must be 4 vertices, 4 faces, and 6 edges. There is no solution for all 6-vertices or greater.

Just for fun, let's find it for all 2-vertices through all 5-vertices. For all 2-vertices, we get V - (2 V) / 6 = 2, so V = 3, F = 2, and E = 3. For all 3-vertices, of course, we already found V = 4, F = 4, and E = 6. For all 4-vertices, we get V = 6, F = 8, and E = 12. And finally, for all 5-vertices, we find V = 12, F = 20, and E = 30. Now they just need to be found for combinations of degrees of vertices.

bleuprint

2009-May-03, 05:46 PM

I don't want to interrupt now with my prejudices and prefer to be a spectator for a while.

The teaser has also the following relation with the 4CT:

"The vertices of a MPG (all regions triangles) are 4-colorable if for any MPG we can add vertices of degree 3 in some of the triangles, so that the degrees of all its vertices are divisible by three". It's the dual of a conjecture about cubic graphs by Hadwiger (1957).

Please go on with the discussion.

bleuprint

grav

2009-May-03, 09:36 PM

Okay, let's see. So far we have V - F / 2 = 2, giving F = 2 (V - 2), so F must be even. Also, V - E + F = V - E + (2V - 4) = 3V - E - 4 = 2, so E = 3 (V - 2), so E must be a multiple of 3. If V is even, then F must be a multiple of 4, as you found earlier, Hh, and E must be a multiple of 6. We can build a chart from this. In terms of a whole number z and F = 2 z, we can determine that E = 3 z and V = z + 2. We can also determine that if the vertices have degrees that are 3n + 3, where n = 0 for 3-vertices, 1 for 6-vertices, etc. , whereas it was found earlier that V - S / 6 = 2, then S = 3 (V + N) and V - (V + N) / 2 = 2, so V = N + 4, therefore N = V - 4 = z - 2. Below is a chart according to z.

z F E V N

1 2 3 3 -1

2 4 6 4 0

3 6 9 5 1

4 8 12 6 2

5 10 15 7 3

6 12 18 8 4

7 14 21 9 5

8 16 24 10 6

9 18 27 11 7

10 20 30 12 8

It can be seen that these are the same figures as we came up with for graphs with all 2-vertices through 5-vertices, so its possible this chart might hold for all graphs, at least triangular ones, regardless of the degrees of the vertices. I will try to find out. So now, if we know any one of the values for V, F, E, or N, we can find the other three, as it will be somewhere on the chart according to the value of z. As far as N goes, we can see that a graph with vertices of a multiple of 3 with 2 faces is not possible, for instance, N being -1, with 4 faces it can only be done with 4 3-vertices, 6 faces requires 4 3-vertices and 1 6-vertice, 8 faces 4 3-vertices and 2 6-vertices or 5 3-vertices and 1 9-vertice, etc. I still see nothing so far that prohibits a triangular graph with an odd number of vertices of a multiple of 3, but I'll keep looking. I have yet to construct a graph with 6 faces, 9 edges, and 5 vertices, 4 being 3-vertices and one being 6-vertices, however, or a graph with 10 faces, etc.

grav

2009-May-04, 12:35 AM

Well, it looks like the chart holds regardless of the degrees of any of the vertices in a planar triangular graph. If S is the sum of the degrees of all of the vertices, then S / 2 = E and S / 3 = F. Therefore we still have 3F = 2E, so E = 3F / 2. Also, V - E + F = 2, so V - 3F / 2 + F = 2, and therefore V - F / 2 = 2 still holds as well. Now, if we make F = 2z, then E = 3z and V = z + 2, same as we had before.

Only the value of N in the chart will be different, since it is made specifically for only vertices with degrees of a multiple of 3. I can see now, looking at the chart, that some configurations will be impossible for degrees of 3-vertices. For instance, we cannot have a 6 faced graph, because that requires 4 3 vertices and 1 6-vertice, for 5 vertices in all. The 6-vertice, however, by itself, requires 7 vertices in the graph, one for itself and 6 more to connect to, which are not present. That goes for a graph with 8 faces for the same reason. Also, a 9-vertice is not possible until we have at least 10 vertices in all, which does not occur until we reach 16 faces. That means that if we were to construct a graph with 10, 12, or 14 faces, which are so far still conceivably possible, we would have to use 4 3-vertices for each of those, and 3, 4, and 5 6-vertices, respectively. So far on the low end of the scale, I've only been able to construct a graph with 4 faces and 4 3-vertices, one with 12 faces, 4 3-vertices, and 4 6-vertices, and one with 16 faces, 4 3-vertices, and 6 6-vertices. The total number of vertices is even in each case.

bleuprint

2009-May-05, 09:51 PM

Hi Grav,

here is an easy way to construct such graphs:

Start with the left graph in the attachment, and replace successively a triangle with the graph in the middle. In this way one can make graphs with 4, 8, 12, 16... vertices.

Replace with the graph to the right. In this way one can make graphs with 4, 10, 16, 22... vertices.

Combining both gives such graphs with any even number of vertices (except 6).

But it does not at all proof that it's NOT possible for an odd number of vertices and I'm eager to see if your approach will succeed?

bleuprint

grav

2009-May-06, 12:45 AM

Hi Grav,

here is an easy way to construct such graphs:

Start with the left graph in the attachment, and replace successively a triangle with the graph in the middle. In this way one can make graphs with 4, 8, 12, 16... vertices.

Replace with the graph to the right. In this way one can make graphs with 4, 10, 16, 22... vertices.

Combining both gives such graphs with any even number of vertices (except 6).

But it does not at all proof that it's NOT possible for an odd number of vertices and I'm eager to see if your approach will succeed?

bleuprintWell, so far I don't seem to have added much to the discussion except to make a chart where any triangular planar graph can be based upon a whole number z where F = 2z, E = 3z, V = z + 2, and S = 6z. These values are regardless of the degrees of any of the vertices, however, so says nothing about all vertices with only degrees of a multiple of three. All it shows so far is that the number of faces must be even, the number of edges must be divisible by three, and the sum of the degrees of all the vertices must be divisible by six.

Mathematically, one could still potentially construct a triangular plane graph with an odd number of vertices all multiples of three, since there is nothing that shows otherwise so far. For instance, let's say we wanted to construct one with seven vertices, which would therefore have to be 4 V3's and 3 V6's. One could potentially connect each of the V6's to each of the other two and also to each of the 4 V3's, for six vertices in all for each of them. None of the V3's attach to each other, only to each of the V6's, so that's three vertices each for them. So it works out in such a representation, but upon actually trying to draw such a graph, one finds they cannot connect in such a way without a couple of the lines crossing each other and making additional vertices in the process. It would work out three dimensionally, but not planar. But that doesn't necessarily mean that the same would occur with more complex graphs. So doing it in this way, we would need something more along the lines of a geometrical proof than a mathematical one.

Your last post gave me an idea, though. The outer perimeter obviously must be a triangle and then we just start filling it in with the ways you suggested. There must be a limited number of ways we can do this, I would think, so if we could identify all of those possible ways, maybe we could determine how the graph must be built up in terms of the number of edges, faces and vertices that are gained with each step, and what must be done to produce only vertices with degrees of multiples of three. So far, it looks like your first image simply runs edges from each of the existing vertices inside of a triangle to make three faces from the one, three more edges, and an additional vertice. Your second image appears to do the same, but with the now smaller triangles. The third image opens up a particular vertice, or we could have started with seven triangles within the original and then run the extra edges inside three of them. If we could identify all of the possible ways of doing this and are sure not to leave any out, that might lead somewhere, perhaps.

grav

2009-May-06, 06:53 AM

Ahah. :) There is no way we could identify all of the possible ways there might be to open vertices and inscribe more triangles and so forth within a graph and be sure we got them all, in order to know there is now other way it can be done without obtaining an odd number of vertices, but there is a way to build up one triangle at a time. Since every face must be a triangle, including the outer region, then all edges where two triangles meet must be the same length, so that they also share the same two vertices at the ends of the same edge. That simplifies things a bit. It means that if we start with a single triangle and build up from there one triangle at a time, there are only two ways triangles can be added. Either the new triangles shares an edge with a single existing triangle, or it shares two of its edges with the edges of two existing triangles, which I will call opening a triangle and closing a triangle, respectively, as shown in the image below.

Now, when a triangle is opened, the outer perimeter will gain one edge and one vertice. When a triangle is closed, the outer perimeter loses one edge and one vertice. The first triangle has three edges and three vertices and that is what we must end up with when the graph is complete as well, so we must open the same number of times as we close to achieve this. Also, when a triangle is opened, the entire graph gains one vertice, two edges, one face and four degrees for the sum of the vertices. When closed, the entire graph remains the same for the vertices, and gains one edge, one face, and two degrees for the sum of the vertices. One triangle starts off with three vertices, three edges, two faces, and six degrees, and since we must open as many times as we close, that means that if we open and close z times from the original triangle, figuring that for z = 1 with the original triangle, the graph will end up having 2 + (1 + 0) z vertices, (2 + 1) z edges, (1 + 1) z faces, and (4 + 2) z for the sum of the degrees, as found before.

Now, since there are only two ways to add triangles, we can just concentrate on the vertices on the perimeter. If we pick one, we just continue to open triangles around it until the vertice we picked has gained the number of degrees that we desire for it, which is some multiple of three. Then we close that vertice with another triangle as shown in the image. Each time we close a triangle, we lock away a vertice within the graph. We simply continue doing this until all of the vertices that were on the perimeter are locked away except for three which have degrees some multiple of three as well. When we have done that, the graph is complete.

I still haven't worked out any mathematics for that yet, but things are getting simpler. At this point I can go ahead and write a program that randomly opens and closes triangles, locking away vertices in multiples of three and so forth, to see if it can come up with a counterexample. The way I will do this is to have it start with just a single triangle, have it pick a vertice on the perimeter, assign a multiple of three degrees to it, and start opening more triangles around it until it reaches that degree and then close the vertice with a closing triangle. Then do the same to another triangle and so forth. If the graph gets too big I will have it start closing vertices more quickly until it gets down to three on the perimeter. Another way I might have it do it also is to just open triangles at random and then have it check vertices for multiples of three and close them.

The programming itself will be easy. The vertices on the perimeter will all be in order going around the perimeter. When a triangle is opened, the program will add a degree to each of two adjoining vertices and squeeze in another vertice between them with two degrees starting off. When the program closes a triangle, it will delete one vertice and add a degree to each of the vertices on either side. Of course, it will keep track of the number of all the vertices added along the way to the graph as a whole in order to know if the total number was even or odd. Here's an example. Let's say we want to get the graph you had in the first image a couple of posts back. We start off with a single triangle. So there are three vertices with degrees 2 , 2 , 2 . Then we open a triangle, so now we have 2 , 3 , ... 2 ... , 3 . The ... 2 ... is the new vertice added with two degrees and we add one degree to the vertices on either side. Then we close one of the ones with 3 degrees and get 3 , - , 3 , 3. One of the V3's is locked within and we add one degree to the vertices on either side. There are now three vertices left on the outer perimeter and they all have degrees which are multiples of three, so we can stop there and we have a graph with four vertices. I will write the program for that tomorrow.

grav

2009-May-07, 11:47 PM

Okay, I ran the second program in the post above. Each graph started with three vertices with degrees of two each. Then it randomly opened new vertices on the perimeter or closed them if they had degrees in multiples of three, while adding a degree each to the vertices on either side. The program ran about five thousand graphs a minute and I let it run for ten minutes, producing about fifty thousand completed graphs in all. If the number of current vertices that were open on the perimeter of a graph exceeded 190, however, the entire graph was deleted and it started over in order to save memory and time. That was about a third of them, so there were actually about seventy-five thousand graphs plotted in all. Of the fifty thousand that completed, about three-quarters of them ended up being just the simple four face graph with four V3's, a sixth of them had eight faces and six vertices, one out of 22 had twelve faces and eight vertices, one of 45 had sixteen faces and ten vertices, etc. That is just how the randomization for the program worked out. The largest graph that completed had 204 faces. It kept track of the number of faces, edges, and vertices, and all of them worked out correctly according to the previous equations for those. If a graph ever completed with an odd number number of vertices, the program was designed to stop. It never did.

You may be surprised to see a graph with eight faces and six vertices on the list. That is because the set of rules that apply to the program aren't quite as strict as those that apply to a straight-line triangular graph, since it allows edges that aren't straight, but can be curved. All that matters for the rules of the program is that every face contains three vertices and that each vertice has degrees of a multiple of three. By reading through the output of the program in a manner probably similar to that of reading through the code in the movie "The Matrix" :), one finds it to produce the graph in the image below. If the rules are a little lax, it's still okay, though. It just means the program allows for a larger set of possibilities than just for that which we are trying to find for triangles. But as long as the smaller subset is contained within the larger set of the program, and still gives the same results, we are fine. In other words, since even the larger set only gives the total number of vertices for a graph in multiples of two, I think it's safe to say that the theorem as applied to the subset is correct.

So now we have turned the even vertices theorem for a triangular planar graph into that of pure mathematics as applied to a linear row of numbers. Well, actually it would be a chain of numbers for the degrees of the outer vertices of a graph as they would wind around the perimeter, but that is just a technicality. We can still use a row of numbers and if we open a vertice at the end of the row, for example, we would just have to add one vertice each to the one before it and the one at the beginning of the row. Anyway, the new proof of the theorem is now this. If we start with a row of three 2's, by using one of two methods at a time, either placing another 2 between two of the others and adding 1 to the numbers to each side of it, or by crossing out a number which is a multiple of 3 and adding 1 to the numbers to each side of it, until one reaches a point where only three numbers remain in the row where each is a multiple of 3, prove that there will always be an odd amount of numbers that have been crossed out or an even number when including the three that are left.

bleuprint

2009-May-08, 07:39 AM

You may be surprised to see a graph with eight faces and six vertices on the list. That is because the set of rules that apply to the program aren't quite as strict as those that apply to a straight-line triangular graph, since it allows edges that aren't straight, but can be curved.

YES that's a surprise, and in fact they are also regular graphs if double edges are allowed (it's a condition for straight line drawings that double edges are not allowed). Drawn on a sphere they look very normal. Putting the two vertices with double edges on opposite points of the sphere we can split one of the double edges an place another copy (or half of it) in between. Then it's also possible with triple or multiple edges.

I'm looking to see if more can be done with your row of numbers.

bleuprint

grav

2009-May-08, 11:16 AM

YES that's a surprise, and in fact they are also regular graphs if double edges are allowed (it's a condition for straight line drawings that double edges are not allowed). Drawn on a sphere they look very normal. Putting the two vertices with double edges on opposite points of the sphere we can split one of the double edges an place another copy (or half of it) in between. Then it's also possible with triple or multiple edges.

I'm looking to see if more can be done with your row of numbers.

bleuprintI'm thinking that in order to gain only straight line triangular graphs, where multiple edges are not allowed, we could place a condition on the row of numbers that vertices cannot be opened or closed between the same two vertices on each side that have already been opened previously. In the program, this could be accomplished with another array that keeps track of every set of two vertices that another vertice has been opened between. By hand, it could be done by lettering each of the vertices as they are created and writing the letters of the sets of two that have been opened to the side of the paper or something as we go and making sure they do not repeat. Lettering vertices would also help in keeping track of the vertices in the row of numbers when doing it by hand anyway, and especially when drawing the graph for it afterward. As I said, though, none of that matters in the proof, however, since the larger set also demonstrates the same thing for the even number of vertices as the subset it contains for the straight line triangular graphs, so I will probably just concentrate on finding the rest of the proof for that with the row of numbers now if I can.

mugaliens

2009-May-10, 12:29 PM

So you only need four color's to color a map? What if all the localaties met at a single point? See the attached diagram. Lets a ssume the lines are perfect and borders intersect at a single point. Would that mean that more than 4 colors are needed?

No. The theorem addresses the issues of adjacent borders, not points.

hhEb09'1

2009-May-10, 04:00 PM

mugs, you have just answered a post that was answered over three years ago! pay attention :)

bleuprint

2009-May-10, 09:38 PM

To mugs and others coming in late.

This restart from #384 is about version3 of this paper (http://arxiv.org/abs/0802.1535)on the 4CT (but version1 is less confusing).

The last replies are about an added teaser in #393, with a new approach on it by Grav from #418.

bleuprint

mugaliens

2009-May-11, 01:18 AM

mugs, you have just answered a post that was answered over three years ago! pay attention :)

Well, hey - I didn't necromance it back into existence! Besides, isn't this like post 431? Do I have time to wade through such a lengthy thread?

How about if I instead review the first couple and the latest dozen posts and chime in?

hhEb09'1

2009-May-11, 01:53 AM

Well, hey - I didn't necromance it back into existence! Besides, isn't this like post 431? Do I have time to wade through such a lengthy thread?It's been sporadic sometimes, but I don't think that there's much necromancy involved with this thread. It's been living and breathing the whole time. :)

How about if I instead review the first couple and the latest dozen posts and chime in?Please, stay!

I just meant, it was answered in the second post to the thread. :)

Jens

2009-May-11, 05:18 AM

mugs, you have just answered a post that was answered over three years ago! pay attention :)

In that case, could I ask a question as well? Will the theorem still work for, say, four different shades of blue?

01101001

2009-May-11, 05:49 AM

In that case, could I ask a question as well? Will the theorem still work for, say, four different shades of blue?

I think this topic is on the surface of a torus.

Therefore it will take 7 shades of blue.

mugaliens

2009-May-11, 07:06 AM

How many different colors would it take on a Klein bottle?

HenrikOlsen

2009-May-11, 02:42 PM

How many different colors would it take on a Klein bottle?

I'm pretty sure I can force 7.

ETA I think I've made one that requires 7.

Basically by extrapolating from the simple 7 color map for the torus.

ETA There's a point-to-point mapping between the surfaces of a torus and a Klein bottle which preserves adjacency and connectedness so 7 it is.

bleuprint

2009-May-11, 05:46 PM

Grav is doing original interesting work (starting at #418) on the following:

"Are there any triangulated planar graphs with an ODD number of vertices and all degrees divisible by 3"

If you can add something on this topic PLEASE join the discussion, otherwise observe it untill your moment (and let's hope it's supreme) has come.

bleuprint

hhEb09'1

2009-May-12, 05:44 PM

otherwise observe it untill your moment (and let's hope it's supreme) has come.

bleuprintWhat is it that you are requesting here, bleuprint?

bleuprint

2009-May-14, 06:55 PM

What is it that you are requesting here, bleuprint?

Ok, that was a joke just as the replies #433 to #436 (I had the impression to have seen them elsewhere on a forum).

Sorry if it was not funny.

Please let the discussion go on.

bleuprint

Dragon

2009-May-18, 10:24 AM

Well, first of all I would like to express thanks to everyone who waited and insistently kept reminding me to post my proof here once I figure out whether it works. It doesn’t, so here it is: see if you can figure out where the mistake is (though please take the time to read and see if anyone posted the same mistake before you). The forum only allows image attachments, and I cannot extract the images from the wordpad document, so I only post text (even without subscripts and all), and I will see if I can get a moderator to attach the RTF file for me. I will reply to attempts to find the mistake and attempts to correct it time permitting.

Theorem 1

Let G be a connected planar graph. Then there is a vertex of G whose degree is at most 5. (Brualdi 516: Theorem 13.2.2)

Theorem 2

Let there be given a k-colouring of the vertices of a graph H = (U, F). Let two of the colours be red and blue, and let W be the subset of vertices in U which are assigned either the colour red or the colour blue. Let Hr, b be the subgraph of H induced by the vertices in W and let Cr, b be a connected component of Hr, b. Interchanging the colours red and blue assigned to the vertices of Cr, b, we obtain another k-colouring of H. (Brualdi 520: Theorem 13.3.1)

For plagiarism purposes, this proof was based on the four-colour proof in Brualdi.

Proof:

Let G be a planar graph of order n. Let X(G) be the chromatic number of G. If n ≤ 4, then X(G) = 4. Now, let n > 4, and the theorem is proven by induction on n. Assume G is drawn in the plane as a plane-graph. By Theorem 1, there is a vertex x whose degree is at most 5. Let H be the subgraph of order n-1 of G induced by the vertices that are different from x. By the induction hypothesis, there is a 4-colouration of H. This proof will show how to colour x so that G is four-colourable. Henceforth, the word «y-vertex» refers to yi, 1≤i≤5, an area of colour n adjacent to x:

Let p, q, r, and s denote distinct integers from 1 to 5. Let 1, 2, 3, 4, 5, a, b, c, d, and e denote colours of the map, not necessarily distinct but all one of the four colours used to colour the map. The only exception is that 1 through 5 denote integers in the following: indices of y, and when in an equation with «≡», or when preceded by «Theorem», «Case», or a form of «be».

Let H(a, b) denote the subgraph of H induced by vertices of H that are assigned either the colour a or the colour b. We say that y-vertices yp, yr Є C*(a, b) if yp and yr are in the same connected component of H(a, b), where a and b are distinct, and yp and yr are distinct and nonadjacent. We say that yp, yr Є C(a, b) if yp, yr Є C*(a, b), and yp and yr are different-coloured. (Note that «Є» implies not only set membership, but also a relationship between yp and yr.)

The condition of yp and yr to be non-adjacent, by definition of C*, allows us to define a y-vertex yq «between» them: consider p-r mod 5: if p-r ≡ 1 or ≡ 4 mod 5, yp and yr are adjacent; if p-r ≡ 0 mod 5, they are non-distinct, therefore of the same colour, a contradiction; if p-r ≡ 2 mod 5, q ≡ p-1 mod 5; if p-r ≡ 3 mod 5, q ≡ p+1 mod 5.

Given distinct colours a, b and two y-vertices yp coloured a and yr coloured e, if yp, yr Є C(a, b) (note: this means e=a or e=b), renumber so that y1 = yp, y2 = the vertex between yp and yr, y3 = yr, and the other two y-vertices are y4 and y5. Let the colour of y2 be d. Then a, b, and d are distinct. Then if a, b, c, and d are distinct, y2 cannot be in a two-colour connected component of H(c, d) with a non-adjacent y-vertex ys (so s≡4 or 5). This is because either one of y2 and ys would be inside the chain of H(a, b) connecting y1 and y2, and the other one would be outside. Also, since y4 and y5 are adjacent, they cannot be Є C*(c, d). So if a, b, c, and d are distinct, «yp, yr Є C*(a, b) implies there are no y-vertices yq, ys such that yq, ys Є C(c, d)» (keep in mind that by definition, p, q, r, and s are distinct). Note: Theorem 2 is equivalent to: if yq, ys ∉ C*(c, d), the colour of yq can be changed to that of ys without changing the colour of ys.

The requirement that a, b, c, and d be distinct is necessary because a and b are always distinct, as are c and d; if one of a or b is equal to one of c and d, say b=c, then yp, yr Є C(a, b), and yq, ys Є C(c, d), could both be true, the connected components of H(a=b, c) and H(c, d) intersecting at a vertex of colour b=c.

We say yp, yq, yr Є C(a, b) if two of yp, yq, and yr are Є C(a, b), and the third is in the same connected component of H(a, b) as the first two. Corollary: If there is only a pair of same-coloured y-vertices, then given three adjacent vertices yp coloured a, yq coloured b, and yr coloured c: yp, yq, yr ∉ C(a, b); yp, yq, yr ∉ C(b, c); yp, yq, yr ∉ C(a, c). Proof: If three vertices are in the same connected component, two of them must share a colour. Since yp and yq are adjacent, and yq and yr are adjacent, yp and yr must share a colour, so a=c. Then, given d, e Є {a, b, c}: yp, yq ∉ C(d, e) because yp and yq are adjacent; similarly, yq and yr ∉ C(d, e); last, yp, yr ∉ C(d, e) because they are of the same colour. So yp, yq, yr ∉ C(d, e).

The proof of the theorem. To start the proof, if the degree of x is 3 or less, assign the one of the 4 colours that is not adjacent to x and obtain a four-colouration of G.

Now suppose the degree of x is 4: there are 4 y-vertices adjacent to x. If two of these are of the same colour, the above process can be used to assign a colour to x and obtain a four-colouration of G. If no two y-vertices are of the same colour, consider the subgraph H(1, 3). If y1, y3 ∉ C(1, 3), apply theorem 2 to change the colour of y1 to 3. Then, there is an available colour, 1, to assign to x, resulting in a four-colouration of G. If y1, y3 Є C(1, 3), then y2, y4 ∉ C*(2, 4), by result above: either y2 is inside the chain of H(1, 3) and y4 is outside it, or vice versa. Then, apply theorem 2 to change the colour of y2 to 4, freeing the colour 2 for x and a four-colourable G. Thereby, a colour is assigned to a vertex x when its degree is 4.

Now, consider the case if the degree of x be 5. Since X(G)≡4 and degree of x is 5, at least two of the y-vertices would have to be of the same colour. If more than two y-vertices share a colour, then there are less than four colours used by them, and therefore there is a free colour to assign to x. Assign that colour to x, and the new graph is four-colourable.

If there do not exist y-vertices yp and yr such that yp, yr Є C(a, b) for some a, b, then switch the colour of a vertex yq between two vertices of the same colour to a colour of a nonadjacent vertex ys. Obviously, since there’s only a pair of same coloured vertices, yq and ys are of different colours, so were yp, yr Є C*(a, b), then also yp, yr Є C(a, b). So yp, yr ∉C*(a, b) implies the colour of ys does not change. Then, assign the previous colour of yp to x.

Now, if there exist such vertices, for the proof, first renumber so that y1, y3 Є C(a, b). This can be done because if yp, yq Є C(a, b), either p-r ≡ 2 mod 5 or p-r ≡ 3 mod 5. In the first case, number 3≡p and 1≡r; in the other case, number 1≡p, 3≡r. «Prime» the colours, which means name them 1, 2, 3, 4, and 5 such that the colour of y1 is 1, the colour of y2 is 2, &c. Now, consider all the possibilities for a, b. Case 1: If y1, y3 Є C(1, 2) or y1, y3 Є C(1, 4) or y3, y1 Є C(3, 2) or y3, y1 Є C(3, 5), then say: yp, yq Є C(a, c), yp is coloured a, yq is coloured b, yr is adjacent to yq and coloured c. Then either b=a or b=c. By definition of C, b≠a, and because yq and yr are adjacent, b≠c. Case 2: If y1, y3 Є C(1, 5), either 3=1 or 3=5; 3≠1 by definition of C; so 3=5; then, y1, y3 Є C(1, 5=3), so y2, y4 ∉ C(2, 4), so colour y2 4 and x 2. If y1, y3 Є C(3, 4), then 1≠3, so 1=4, and y1, y4 Є C*(3, 1=4). Then y2, y5 ∉ C(2, 5), so colour y5 2 and x 5. Case 3: If y1, y3 Є C(2, 4), y1, y3 Є C(2, 5), or y1, y3 Є C(4, 5), say y1, y3 Є C(a, b), and the colours of the five vertices are 1, 3, a, b, c. Since y1 and y3 are of different colours, either 1=a and 3=b or 1=b and 3=a; in either case, only 3 colours (1=a, 3=b, 5 or 1=b, 2=a, c) are used, so there is a free colour to assign to x.

The only case left is y1, y3 Є C(1, 3). Now if y1, y4 Є C*(1, 4), «shift», or renumber y4 as y1, y5 as y2, y1 as y3, y2 as y4, and y3 as y5. Prime. So y3, y5 Є C(3, 5), and y1, y3 Є C*(1, 3). Consider y1, y4. If y1, y4 Є C*(1, 4), shift and prime again. Now y1, y3 Є C*(1, 3), y3, y5 Є C*(3, 5), and y5 and y2 Є C(2, 5). If y1, y4 Є C*(1, 4), because y3, y5 Є C*(3, 5), either 1=3, 1=5, 4=3, or 4=5. Otherwise, one of y1 and y4 would be outside a chain of H(3, 5) and the other one inside, or the other way around. Because y1 and y5, y4 and y3, and y4 and y5 are adjacent, we must have 1=3. But, we have y1, y3 Є C*(1, 3), and by definition of C*, 1≠3. So we have shown that we can label the graph so that y1, y3 Є C(1, 3) and y1, y4 ∉ C*(1, 4).

Now, we consider the different same-colour combinations and show a way to colour the vertices in each case. Because their vertices are adjacent, 1≠2, 2≠3, 3≠4, 4≠5, and 1≠5. Because y1, y3 Є C(1, 3), 1≠3. If 2=5, since because we have established y1, y4 ∉ C*(1, 4), we can colour y4 1 and x 4. If 3=5, y1, y3 Є C(1, 3=5) implies y2, y4 ∉ C(2, 4), so colour y4 2 and x 4. If 1=4, then y1, y3 Є C(1=4, 3) implies y2, y5 ∉ C(2, 5), so colour y2 5 and x 2. If 2=4, then: if y3, y5 ∉ C(3, 5), colour y3 5 and x 3.

The only case left is 2=4; y1, y3 Є C(1, 3); and y3, y5 Є C(3, 5). This is the case where Alfred Kempe messed up. Now, we consider whether changing the colour of y2 to 5 would make y1, y4 Є C(1, 2=4) and whether changing the colour of y4 to 1 would make y2, y5 Є C(2=4, 5). If neither is true, simply colour y2 5, y4 1, and x 2=4. Otherwise, several options are possible. In one of them, change the colour of y2 to 1, thereby changing the colour of y1 to 2. If y1, y3 Є C(2, 3), then y2, y5 ∉ C(1, 5), so colour y2 5 and x 1. The colours of y-vertices in order are 2, 5, 3, 2, 5. If y1, y3 ∉ C(2, 3), because only the colours 1 and 2 were switched, y3, y5 Є C(3, 5), so y2, y4 ∉ C(1, 2=4), and changing the colour of y4 to 1 would not make y2, y4 Є C(1, 2=4). So colour y4 1, then y3 2 (since y1, y3 ∉ C(2, 3)), and x 3. The colours of y-vertices in order are 2, 1, 2, 1, 5. Now, numbers no longer denote colours.

The process outlined solves a long-existing problem. Whereas the 1976 proof used about 1000 hours of computer time, this proof may be followed by a mathematician in as little as half an hour.

Bibliography:

Brualdi, Richard A. Introductory Combinatorics. Upper Saddle River, NJ:

Prentice-Hall, Inc., 1999.

[/SIZE][/FONT]

hhEb09'1

2009-May-18, 01:39 PM

[FONT=Fixedsys]Well, first of all I would like to express thanks to everyone who waited and insistently kept reminding me to post my proof here once I figure out whether it works. It doesn’t, so here it is: see if you can figure out where the mistake is (though please take the time to read and see if anyone posted the same mistake before you). As interesting as this problem is, that's a pretty complicated proof. I'd prefer you just point out your error rather than we spend time on what is an admittedly inadequate proof. There may be other errors, but one is enough. :)

The forum only allows image attachments, and I cannot extract the images from the wordpad document, so I only post text (even without subscripts and all), and I will see if I can get a moderator to attach the RTF file for me. You may provide a link to the file. I doubt if the file (with images) is small enough to load onto the BAUT website.

For plagiarism purposes, this proof was based on the four-colour proof in BrualdiFor plagiarism purposes? :)

mugaliens

2009-May-19, 07:20 AM

I'd be willing to be it'd take about 9 minutes on a modern desktop...

Dragon

2009-May-21, 08:09 AM

As interesting as this problem is, that's a pretty complicated proof. I'd prefer you just point out your error rather than we spend time on what is an admittedly inadequate proof. There may be other errors, but one is enough. :)

Well, I do not want to spoil the fun, so to give a hint, I will tell that the error is toward the end. Very much toward the end in fact.

You may provide a link to the file. I doubt if the file (with images) is small enough to load onto the BAUT website.

As a matter of fact, with images that I made myself, the filesize is 100 kB.

For plagiarism purposes? :)

Like most papers require people to cite sources and stuff. That’s what I meant.

bleuprint

2009-May-22, 05:51 PM

To Dragon

Well, I do not want to spoil the fun, so to give a hint, I will tell that the error is toward the end. Very much toward the end in fact.

Please make it more understandable, so we can have more fun. To be honest: as formulated now I don't understand it. It needs some layout, some illustrations...

As a matter of fact, with images that I made myself, the filesize is 100 kB.

Please put it somewhere on your homesite (most servers give you some MB together with your e-mail location). One hyperlink then is sufficient.

Like most papers require people to cite sources and stuff. That’s what I meant.

That was understandable and it's always nice to honour other people whenever it's possible.

bleuprint

DoggerDan

2012-Jul-26, 10:42 PM

So you only need four color's to color a map? What if all the localaties met at a single point? See the attached diagram. Lets a ssume the lines are perfect and borders intersect at a single point. Would that mean that more than 4 colors are needed?

The four color theorem covers borders (line segments and curves), not points.

On an interesting side-note, it's also why the first color graphics cards came in four colors. :)

slang

2012-Jul-27, 12:12 AM

The four color theorem covers borders (line segments and curves), not points.

On an interesting side-note, it's also why the first color graphics cards came in four colors. :)

Note: thread necromancy.

DoggerDan: You're responding to a 7 year old post by someone who hasn't logged in since Jan 2009. It's doubtful Matthew will ever see your answer. If I'm wrong... Hi Matthew, welcome back!

worzel

2012-Jul-31, 12:43 PM

On an interesting side-note, it's also why the first color graphics cards came in four colors. :)

That sounds very interesting. Can you elaborate?

NEOWatcher

2012-Jul-31, 04:55 PM

That sounds very interesting. Can you elaborate?

I'd like to see an elaboration of that too. I'm not convinced it's "why", but more of a convenient coincidence because it can also be represented with patterns (and was already practiced that way because of the long history of monochrome displays)

4 is just the next bit past monochrome and allows for 4 pixels per byte.

Strange

2012-Jul-31, 05:25 PM

4 is just the next bit past monochrome and allows for 4 pixels per byte.

That was my assumption too (but my experience with computer graphics starts with 8-bit (256 colour) systems).

Powered by vBulletin® Version 4.2.3 Copyright © 2021 vBulletin Solutions, Inc. All rights reserved.