Question about the 'four color theorem'

[Kyriakos]

Might post in the science forum if i have more stuff to ask, but currently i only have a general question and more people are likely to see the thread here, so...:

The four color theorem generally states than any planar map (a plane, 2d, which isn't infinite in any of the two directions?) divided into always bordering regions (ie no part of the plane is empty) can always be colored with up to 4 colors and no two adjacent regions will have the same color regardless of how the regions look like or how many they are. Borders which are a single point do not count as making their respective regions adjacent.

My question is if this includes borders that are themselves not a singular point, but at the same time are part of a side (curved or line) of a region, ie their graph would have infinite points in a line. More generally (i think?) the question is if each individual region can be made up of perimeters/borders which themselves tie in this way to infinity. Obviously this makes the question different than one where any region has to be seen as tied to a meter, instead of tied to an equation.

From what (very little) i read of the theorem, the attempts to *officially* prove it (currently afaik it is somewhat proven with the help of computers, but this has issues for the math community) follow a pattern of first providing a number of example maps where four colors are enough, then showing that any counter-example map would have to include those first maps as part of it. Anyway, i would be happy if my question can be easily and correctly answered, and i am sure it can given the definition of the theorem is not in debate

(btw, do excuse any possible error on my part in the synopsis above )

 

[warpus]

Can you maybe illustrate your question? I am having a hard time making sense of it, but I sort of half remember proving all this stuff in university. Not sure if the details will come back to me, but who knows.

My question is if this includes borders that are themselves not a singular point, but at the same time are part of a side (curved or line) of a region, ie their graph would have infinite points in a line.

Are you asking if a region can just be a line or curve? If so, I think the answer is no.

 

[Kyriakos]

^Yes, that was what i meant (not clearly stated, i know..). Apparently it likely is "no", although in another forum i got the info that some proof using computers - thus still not a final math proof- possibly (?) includes such parts of regions as well.

An example of such a regional part would be the y axis when x--> 0 here:

Ie i wanted to know with certainty if in the theorem you can have regions that also feature some linear bit that itself would be taken to be a whole 'corner' and not having just a single point as corner.

 

[warpus]

The theorem we learned in school was one where each region was one you could colour in - so it couldn't be a line. But if what you say is true, then the theorem extends to graphs with such regions as well.

 

[Kyriakos]

^Apparently not even the more specific version (no such borders allowed) has been proven without some use of computers

 

[warpus]

Interesting, maybe we didn't do a full formal proof. This was actually in a class where I got the highest mark, in university, out of all my required courses - Combinatorics 281. or 283. Or something like that. Anyway, it was all about graphs and graph theory, as well as counting methods. Fun class, you either seemed to get it or you didn't, and for some reason I got it.

 

[onejayhawk]

IIRC there was a proof for more than a largish number of regions and proof for small numbers. The final proof literally tested all the ones in the middle using 1970s mainframe computers. These days you probably model it on your phone.

J

 

[Kyriakos]

^Those are proofs needing computers to check, which rely on a hypothesis limiting the cases they have to check (cause no computer can check 100 billion cases, etc), but i am not sure if even the hypothesis of those 'no counter-example maps' is accepted as certainly correct (it might and iirc it is, which still leaves the issue of one not proving it without showing 'all' the cases produce the result via help of computer and not just a math presentation).

I do know that not all mathematicians accept this use of computers, though. ie for finishing a proof.

 

[warpus]

I seem to remember a proof by contradiction, but can offer no details.

 

[Bootstoots]

Interesting, maybe we didn't do a full formal proof. This was actually in a class where I got the highest mark, in university, out of all my required courses - Combinatorics 281. or 283. Or something like that. Anyway, it was all about graphs and graph theory, as well as counting methods. Fun class, you either seemed to get it or you didn't, and for some reason I got it.

I took Combinatorics and had a great time with it, too. It's fun and relatively useful for all sorts of things, especially understanding algorithms and probability. Then I made the mistake of thinking I was good at math, and got clobbered by abstract algebra the next semester.

I think the five- or maybe six- color theorem is easy enough for undergrads to do, so you may have done something like that. I have some recollection of doing one of those as an exercise but can't say for sure if I did.

 

[Rashiminos]

If I understand the question correctly, you're asking if the definition of borderline is restricted for the purposes of the theorem?

Spoiler :

Edit: If my searches are going well enough, the definition implies a simple, closed, piecewise smooth curve, and a curve similar to sin(1/x) may not defined at the chosen endpoints (thus not satisfying the closed criterion).

Edit2: Oh, you're trying to treat the "borders" as regions. Essentially the borders are infinitesimal in width. If the borderlines are widened (resulting in a nonzero area) and together treated as one (or more) regions, then you have a whole new set of borders to deal with, and so on (and the 4ct should work with a recolor, 2-colorable in the case of the OP). Instead of the picture in the OP using black to show borders, it could just have the regions touching each other at the respective borders.

***

https://en.wikipedia.org/wiki/Four_color_theorem
Probably:

In addition, bizarre maps (using regions of finite area but infinite perimeter) can require more than four colors.[2]

http://www.jstor.org/stable/3647828?origin=crossref&seq=1#page_scan_tab_contents

****

Spoiler :

Some possible reading:

On second look it seems you received a more detailed response in another forum.

 

[Kyriakos]

^Thanks

Yes, i doubt that even the more generalised version is trying to view borders as actual regions, although it does view continuous 1d segments and not just points as borders (as with that y when x-->0 in the example), which makes the question more generalised than with more cleanly defined regions. But as noted the more specific version has not been proven rigorously (here i only mean without computer help), and the proof exists in pure math only for 5 colors (it uses polyhedral properties and Euler statements about stable relations there between edges, surfaces and points where edges connect, and some other stuff i did not particularly read about already ).

However it seems that all proofs with use of computer are based on hypothesising a finite and smallish number of representative different maps, and i haven't yet read how they arrive at the conclusion those indeed are finite and smallish-- they need to be so, otherwise the powerful computer won't be enough to check.

 

[Rashiminos]

However it seems that all proofs with use of computer are based on hypothesising a finite and smallish number of representative different maps, and i haven't yet read how they arrive at the conclusion those indeed are finite and smallish-- they need to be so, otherwise the powerful computer won't be enough to check.

The argument attempts to show that if there is a counterexample with a minimum number of regions, then a part of that counterexample must also contain one of the smallish representative maps from which the number of regions can be reduced without changing the number of colors required. This leads to a contradiction since the counterexample should have had the least possible number of regions requiring 5 or more colors.

 

[Kyriakos]

I see. But how do they arrive at the set of example maps? (iirc a few hundred thousands or something?).

 

[Rashiminos]

I see. But how do they arrive at the set of example maps? (iirc a few hundred thousands or something?).

A more detailed explanation would probably require a background in topology on your part (and mine).

The Appel and Haken proof uses 1476 such configurations, and a later one used only 633 (Robertson, Sanders, Seymour, Thomas)

 

[Leoreth]

I think the problem is usually formulated in topology (maps and such), but as far as I know is proven in graph theory. That is, for a given set of vertices connected by edges you can color the vertices using only four colors so that no edge has vertices of the same color.

(In other words, "areas" on the map map to vertices and "borders" that separate two areas map edges that connected the vertices for those areas.)

So the cheap answer is that if your map can be modeled as a graph, then the four color theorem applies. In currently cannot conceive of a 2D map that could not (infinite areas instead of "borders" at the edges are definitely no problem), but my topology is weak, so maybe?

Using non-intuitive definition of area (supposedly a 2D shape) or border (supposedly a 1D shape, so not a fractal or something else weird) only makes the theorem not applicable because it violates the (admittedly rarely explicitly specified) definition of the problem.

 

[warpus]

I took Combinatorics and had a great time with it, too. It's fun and relatively useful for all sorts of things, especially understanding algorithms and probability. Then I made the mistake of thinking I was good at math, and got clobbered by abstract algebra the next semester.

I think the five- or maybe six- color theorem is easy enough for undergrads to do, so you may have done something like that. I have some recollection of doing one of those as an exercise but can't say for sure if I did.

I will never forget when I arrived at my professor's door, a couple days after the exam, to check my mark. He had them all posted on the door, only the final marks though, and not final exam marks. This was a very math and CS heavy university, so every single Math course I ever took was just.. well, sort of insane. My marks ranged anywhere from 34% (2nd year Calculus and stupid stupid stats) to 75%. I had about 75% going into the exam for combinatorics, and did the math beforehand - if I got 83% or so that would mean I got close to 100% on the exam, and if I got 0% on the exam I would just barely pass the class (although it would still mean I fail, due to the failed exam). Anyway, I get there, and.. I look at the sheet. It says 82%. I got 82% in the class. What the hell. I stand there like an idiot and keep looking at my name, tracing the line to the right, and looking at that 82%. "That's got to be wrong!" I thought to myself. The prof was in his office, he noticed I had been standing there for a while looking at his door. "Anything wrong?".. .. I don't remember what I said, but that's how I got the highest mark in my university career (excluding silly subjects like english and history, only including math and cs here), by somehow getting near 100% on the exam. I have no idea how I did it, to this day I'm half convinced he screwed up. I thought it would have been possible to get 85% on that exam, maaaaaybe 90%, but somehow I got something close to 100%. Such an amazing feeling to get a mark like that in a class you actually enjoyed, contrasts quite a bit with the 34% I got in Calculus II (the second time I took it I got something that was in the 40-50% range, and the third time I took it I passed with 50%)

/wall of text

I love abstract algebra mind you, I loved doing abstract proofs that I've never seen before. Stats and calc is what I hated instead. And yeah, I think you might be right about the 5 or 6 colour version, but this was a University where every single math major course is just insane, so.. I wouldn't be surprised if it was more involved than that. But yeah, can't really remember.