Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For the four coloring problem, maps can be pre-simplified removing all faces that have 2, 3 or 4 edges. In this case the Euler identity becomes: $F_5 + 0F_6 = 12 + F_7 + 2F_8 + 3F_9 + …$. One thing that can be noticed is that pre-simplified maps must have a great number of faces of type $F_5$ (with 5 edges) respect to faces of type $F_7$ or greater. For complex maps (containing faces with a lot of edges) many $F_5$ have to exist. For example for a single face with 1000 edges, 994 faces of type F5 must be added to the Euler identity ($F_5 = … + 994 F_{1000} + …$).

One thing that I initially imagined is that these $F_5$ faces were grouped in cluster, in which an $F_5$ face is surrounded only by other $F_5$ faces. Then I realized that $F_5$ faces could also be mixed with faces of type $F_6$ (which do not alter the Euler identity) or with faces of type >= $F_7$.

I was looking for a paper that analyze the distribution of faces in maps (possibly pre-simplified). Can anybody help?

Just for sharing (not related to this question), one thing that I found analyzing this is that simplified maps of 13 faces do not exist.

share|improve this question

2 Answers 2

You can have arbitrary large "partial maps" without any pentagons whatsoever. See the following picture, taken from here:

http://www.mylovedone.com/image/solstice/sum10/HyperbolicCentralPlaceFractals.html

enter image description here

Using this idea you still can get a bona fide "map" with finitely many countries on the sphere. It's just that the pentagons have been moved "far away".

share|improve this answer
    
The "far far away land" it is full also of F4 faces (squares) :-) Nice category of graphs, thanks! –  Mario Stefanutti Jan 31 '13 at 21:33

I think you've misidentified Euler. If $F_n$ is the number of faces with $n$ edges, then you get $$F_5\ge12+F_7+2F_8+3F_9+\cdots$$ From this it is evident, for example, that any (simplified, planar) map must have at least 12 pentagons. Also, if a map has exactly 13 faces, then either they are all pentagons, or there are 12 pentagons and one hexagon. 13 pentagons would imply 13 x 5 / 2 edges which is a nonsense, so that's out. I don't see, offhand, how you rule out 12 pentagons and a hexagon (13 faces, 33 edges, 22 vertices, all of degree 3).

share|improve this answer
2  
I am pretty sure the identity is: $$F_5=12+F_7+2F_8+\cdots$$ Why the ">"? About the simplified map with 13 faces, I verified manually (computer program) that it does not exist. I agree that 13 pentagons is not possible because it would lead to the identity to be 13 = 12. Any other face with more than 6 edges would not work either. If we try with an $F_7$, the equilibrium would bend on the right of the equality and we would need 13 faces of type $F_5$ to balance it. The only possible solutions is to have 12 faces of type $F_5$ + 1 face of type $F_6$ = 13 faces. But these maps do not exist. –  Mario Stefanutti Nov 25 '11 at 9:29
1  
$$F = F_2+F_3+F_4+\cdots$$ $$2E = 3V = 2F_2+3F_3+4F_4+\cdots$$ Since a region bounded by n edges has n vertices and each vertex belongs to three regions, by Euler's formula V-E+F = 2 we have: $$6V-6E+6F = 12$$ $$4E-6E+6F = 12$$ $$6F-2E = 12$$ $$6(F_2+F_3+F_4+\cdots)-(2F_2+3F_3+4F_4+\cdots) = 12$$ $$4F_2+3F_3+2F_4+F_5+0F_6-F_7-2F_8-3F_9-\cdots = 12$$ That becomes: $$F_5=12+F_7+2F_8+3F_9+\cdots$$ –  Mario Stefanutti Nov 25 '11 at 9:30
    
Just to make sure I understand: your proof that there are no maps with 12 pentas and 1 hexa is a proof-by-computer? I'm not even sure I see what the search space is. –  Gerry Myerson Nov 25 '11 at 10:24
    
I used a computer program I am building to create simplified maps (sourceforge.net/projects/maps-coloring). The program did not return any map of 13 faces. At the beginning I thought to a bug in the software, then I sketched a proof I thing is right (4coloring.wordpress.com/open-points-and-notes) –  Mario Stefanutti Nov 25 '11 at 10:58
2  
I think the 13-region result appears, along with other results that might interest you, in Ruth A Bari's paper, Maximal $m$-gons in 4-regular major maps, Lecture Notes in Mathematics 186 (1971) 5-8. –  Gerry Myerson Nov 25 '11 at 11:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.