User mario stefanutti - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T09:19:44Z http://mathoverflow.net/feeds/user/14114 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120162/question-about-3-regular-graphs-with-a-restriction-also-fullerene-and-four-color Question about 3-regular graphs with a restriction (also fullerene and four color theorem) Mario Stefanutti 2013-01-29T00:01:54Z 2013-01-29T07:57:31Z <p>(Crossposted from math.stackexchange.)</p> <p>Studying all 3-regular graphs that have only faces with 5 edges or more (simplified), I empirically found (computer program) that many hypothetically possible graphs, that by Euler's identity may exist ($F5 = 12 + F7 + 2F8 + 3F9 + ...$), do not actually exist. Using a VF2 algorithm to filter out isomorphic maps being created, I also noticed that not so many graphs as I expected exist. And that one general category of graphs, that always represents a simplified 3-regular graph, is that of fullerenes (with 12 faces F5 and an arbitrary number of F6). Here is a list of what I found, so far, for each class of graphs, from 12 faces to 20 faces (surrounding area included).</p> <p><strong>The question is</strong>: Since the computation of maps with 17, 18, 19, 20 faces (simplified and not containing isomorphic graphs) it is taking very long time (days of CPU time on a PC), is this sequence already known?</p> <ul> <li>12 faces: 1 (only 1 graph exists) <ul> <li>On 3 dimentional space (sphere) it is a dodecahedron</li> <li>It is a fullerene: 20-fullerene Dodecahedral graph</li> </ul></li> <li>13 faces: 0 (no simplified graphs exist with 13 faces) <ul> <li>The hypothetical (by Euler's identity) map of 12 F5 and 1 F6 <strong>does not exist</strong></li> </ul></li> <li>14 faces: 1 (12 F5 + 2 F6) <ul> <li>he hypothetical (by Euler's identity) map of 13 F5 and 1 F7 <strong>does not exist</strong></li> <li>It is a fullerene: GP (12,2) Generalized Petersen graph</li> </ul></li> <li>15 faces: 1 (12 F5 + 3 F6) <ul> <li>The hypothetical (by Euler's identity) map of 14 F5 and 1 F8 <strong>does not exist</strong></li> <li>It is a fullerene: 26-Fullerene</li> </ul></li> <li>16 faces: 3 (Two graphs are 12 F5 + 4 F6. The other has 14 F5 + 2 F7) <ul> <li>The hypothetical (by Euler's identity) map of 14 F5 and 2 F7 <strong>does exists</strong></li> <li>The other two are Fullerenes</li> </ul></li> <li>17 faces: ???</li> <li>18 faces: ???</li> <li>19 faces: ???</li> <li>20 faces: ???</li> </ul> <p>ADD (28/Jan/2013):</p> <ul> <li>Images of these graphs are here: <a href="http://4coloring.wordpress.com/2013/01/26/four-color-theorem-simplified-maps-and-fullerenes/" rel="nofollow">http://4coloring.wordpress.com/2013/01/26/four-color-theorem-simplified-maps-and-fullerenes/</a></li> </ul> http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph How many "different" colorings (excluding exchanges) exist for a given map (graph)? Mario Stefanutti 2011-04-10T17:07:22Z 2012-12-22T05:24:06Z <p>In particular I'm interested in regular maps, excluding all maps that can be colored with 2 or 3 colors. For what I need to analyze, maps have to be regarded as differently colored, if the same coloring cannot be obtained by subsequent exchanges of colors. In other words, for example, once a map has been properly colored, I don't want to count all other configurations that derive from subsequent exchanges of colors. Since the arbitrary nature of choosing colors, these derived configurations are equivalent (for what I'm analyzine) to the first one, since they could have been obtained just choosing different colors in the first place. Instead, there are colorings that differ in such a way that exchanging colors won't help to transform one configuration into the other. In the following picture the graphs named (A) and (B) are the only ones that cannot be converted into one another by swapping colors.</p> <p><a href="http://4coloring.files.wordpress.com/2011/04/3-colored-in-12-different-ways.png" rel="nofollow">http://4coloring.files.wordpress.com/2011/04/3-colored-in-12-different-ways.png</a></p> <p>My question is: how many "different" colorings (in the meaning I explained) exist for a given map? I've only found an article on <a href="http://en.wikipedia.org/wiki/Graph_coloring" rel="nofollow">http://en.wikipedia.org/wiki/Graph_coloring</a> that count all possible colorings including swaps. Is there a paper that can help me on this?</p> <p>I already posted it to "math stackexchange" but, so far, I haven't received the answer I was looking for.</p> http://mathoverflow.net/questions/63861/representations-of-regular-maps-four-color-theorem Representations of regular maps (four color theorem) Mario Stefanutti 2011-05-03T23:20:50Z 2011-06-08T06:35:12Z <p>For the scope of the four color problem and without lack of generality, maps can be represented in different ways. This is generally done to have a different perspective on the problem.</p> <p>For example, the graph-theoretic representation of maps has become so common and important that generally the four color problem is stated and analyzed directly in terms of graph theory: <a href="http://en.wikipedia.org/wiki/Four_color_theorem" rel="nofollow">http://en.wikipedia.org/wiki/Four_color_theorem</a>.</p> <p>I am trying to collect other representations that may in some way help to get a different point of view on the problem. If you know one of these representations that is not listed and wish to share, report it here. If you also have a web reference that explains or shows the representation, it would be great.</p> <p>The representations have to be general and applicable to all maps with the simplification that only regular maps (no exclaves or enclaves, 3 edges meeting at each vertex, etc.) can be considered.</p> <p>These are some classic representations:</p> <ul> <li>Natural: As a 3-regular planar graph (boundaries = edges)</li> <li>Canonical: As the dual graph of the "natural" representation (region = vertex, neighbors = edges)</li> <li>As a straight line drawing graph (Fáry's theorem)</li> <li>As a graph with vertices arranged on a grid</li> <li>As a rectilinear cartogram</li> <li>As circle packing</li> </ul> <p>Plus, I found these:</p> <ul> <li>As a circular map</li> <li>As a rectangular map</li> <li>As clefs (derived from rectangular maps)</li> <li>As pipes map (derived from the clefs representation)</li> <li>...</li> </ul> <p>Here is an example of some of these representations for the original map shown:</p> <p><img src="http://4coloring.files.wordpress.com/2011/05/representations-of-maps-v2.png"/></p> <p>And here are other representations after the comments received:</p> <p><img src="http://4coloring.files.wordpress.com/2011/05/other-representations-of-maps.png"/></p> <p>UPDATE: 19/May/2011 - Added other representations of graphs</p> http://mathoverflow.net/questions/62328/is-there-a-formula-to-count-how-many-different-topological-regular-maps-can-be-cr Is there a formula to count how many different topological regular maps can be created with n faces (on a sphere)? Mario Stefanutti 2011-04-19T19:58:06Z 2011-04-29T18:00:24Z <p>Notes:</p> <ul> <li>For "regular" I intend maps in which the boundaries form a 3-regular planar graph</li> <li>For "different" I intend maps that cannot be topologically transformed one into another (faces have to be considered unnamed)</li> </ul> <p>I've been looking for a formula, but it is too difficult for me. Maybe it has a simple solution but I don't see it.</p> <p>This was my best guess, but I already know that it is not correct because full of symmetries, as it can be verified manually.</p> <p>General formula:</p> <ul> <li>$2\sum_{s_{(f-3)}=2f-5}^{2f-5+2} \text{...}\sum_{s_2=5}^{s_3} \sum_{s_1=3}^{s_2} s_1\left(s_1-1\right)\left(s_2-3\right)\text{...}\left(s_{(f-3)}-(2f-5-2)\right)$</li> </ul> <p>Examples:</p> <ul> <li>4 faces = $2\sum_{s_1=3}^5 s_1\left(s_1-1\right)$</li> <li>5 faces = $2\sum_{s_2=5}^7 \sum_{s_1=3}^{s_2} s_1\left(s_1-1\right)\left(s_2-3\right)$</li> </ul> <p>Here are the first results that can be found manually (excluding symmetries):</p> <ul> <li>2 faces = 0 possible regular map (an island and the ocean) (not to be counted, because not regular)</li> <li>3 faces = 1 possible regular map (an island with two regions and the ocean) (two islands and the ocean wouldn't be regular)</li> <li>4 faces = 3 possible regular maps (can be verified adding a face from the previous map)</li> <li>5 faces = <del>20 possible regular maps</del> (ERROR: There were duplicates)</li> <li>6 faces = <del>329 possible regular maps</del> (ERROR: There were duplicates)</li> <li>...</li> </ul> <p>These are all maps up to 5 faces (ERROR: contains duplicates):</p> <p><img src="http://4coloring.files.wordpress.com/2011/04/counting-maps-example-v3-named.png" alt="maps"></p> <p>Image for the comment on "triangulations of the sphere"</p> <p><img src="http://4coloring.files.wordpress.com/2011/04/counting-maps-duals-and-triangulations-v3.png" width="321" height="218"></p> <p>And without duplicates:</p> <p><img src="http://4coloring.files.wordpress.com/2011/04/counting-maps-example-v5.png"></p> <p><strong>MODIFIED</strong>: 20/Apr/2011 - Removed "3-connected" from the question. See comment below.</p> <p><strong>MODIFIED</strong>: 21/Apr/2011 - Added a picture with all regular maps up to 5 faces</p> <p><strong>MODIFIED</strong>: 21/Apr/2011 - Added a picture for the comment on "triangulations of the sphere" and multiple edges, related to the dual graph of the original 3-regular planar graph</p> <p><strong>MODIFIED</strong>: 27/Apr/2011 - Manually computed number of different maps of 6 faces = 329, added numerical IDs to the maps </p> <p><strong>MODIFIED</strong>: 29/Apr/2011 - The manual computation of the number of regular maps contains some duplicated (Homeomorphic pairs)</p> <p><strong>MODIFIED</strong>: 29/Apr/2011 - Just to leave things a little more clean (I removed the duplicates ... I hope)</p> http://mathoverflow.net/questions/120162/question-about-3-regular-graphs-with-a-restriction-also-fullerene-and-four-color/120181#120181 Comment by Mario Stefanutti Mario Stefanutti 2013-02-08T22:20:17Z 2013-02-08T22:20:17Z Thanks again. Plantri is really a great program and it is so fast. Where my program takes 1 minute to elaborate all graphs of 15 faces, Plantri is istantaneous. http://mathoverflow.net/questions/120162/question-about-3-regular-graphs-with-a-restriction-also-fullerene-and-four-color/120181#120181 Comment by Mario Stefanutti Mario Stefanutti 2013-01-29T09:58:14Z 2013-01-29T09:58:14Z Thanks. So fast! I'm going to try this program right away. http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph/68735#68735 Comment by Mario Stefanutti Mario Stefanutti 2011-06-28T14:48:58Z 2011-06-28T14:48:58Z Hi, how did you make these computations? I was planning to implement this feature into the program I'm building, but I'm having trouble to eliminate maps that &quot;seems&quot; different but that are actually the same map (Homeomorphic maps). See this other post: <a href="http://mathoverflow.net/questions/62328/is-there-a-formula-to-count-how-many-different-topological-regular-maps-can-be-cr" rel="nofollow" title="is there a formula to count how many different topological regular maps can be cr">mathoverflow.net/questions/62328/&hellip;</a> http://mathoverflow.net/questions/63861/representations-of-regular-maps-four-color-theorem/63864#63864 Comment by Mario Stefanutti Mario Stefanutti 2011-05-06T17:17:38Z 2011-05-06T17:17:38Z I really like this one based on the circle packing theorem, thanks! http://mathoverflow.net/questions/63861/representations-of-regular-maps-four-color-theorem Comment by Mario Stefanutti Mario Stefanutti 2011-05-04T10:34:47Z 2011-05-04T10:34:47Z Hi Paul, I remember a comment made about this question by Noah Snyder. <a href="http://mathoverflow.net/questions/19240/algebraic-proof-of-4-colour-theorem" rel="nofollow" title="algebraic proof of 4 colour theorem">mathoverflow.net/questions/19240/&hellip;</a>. &quot;As far as I know there isn't anyone who is holed up in their attic thinking about only the 4-color theorem, instead there's a lot of people who every time they find a new tool think: hrm, I wonder if this tool would work on the 4-color theorem?&quot; For example check the current reserch of Robin Thomas (<a href="http://people.math.gatech.edu/~thomas/" rel="nofollow" title="algebraic proof of 4 colour theorem">people.math.gatech.edu/~thomas</a>) http://mathoverflow.net/questions/62328/is-there-a-formula-to-count-how-many-different-topological-regular-maps-can-be-cr Comment by Mario Stefanutti Mario Stefanutti 2011-04-27T18:04:55Z 2011-04-27T18:04:55Z I think I located one of the pair you were talking about: 1.1.8 and 1.3.4. You are right, these are the same map! I have to review the manual computation of the count of different maps. I still would like to find a formula to count different maps, avoiding to manually calculate them ... also because this is error prone! Thanks! http://mathoverflow.net/questions/62328/is-there-a-formula-to-count-how-many-different-topological-regular-maps-can-be-cr Comment by Mario Stefanutti Mario Stefanutti 2011-04-27T17:40:51Z 2011-04-27T17:40:51Z Hi jc, I added some numerical IDs to the maps. I wasn't able to pinpoint the pairs you were talking about. Can you specify them using the IDs? I just want to be sure we talk about the same pairs of maps. http://mathoverflow.net/questions/62328/is-there-a-formula-to-count-how-many-different-topological-regular-maps-can-be-cr Comment by Mario Stefanutti Mario Stefanutti 2011-04-27T14:18:16Z 2011-04-27T14:18:16Z Actually it matches this one: <a href="http://oeis.org/A163138" rel="nofollow">oeis.org/A163138</a> (0 does not have to be considered because the map in that case is not regular). But I think 4 terms are just too few and it may be just a coincidence. http://mathoverflow.net/questions/62328/is-there-a-formula-to-count-how-many-different-topological-regular-maps-can-be-cr Comment by Mario Stefanutti Mario Stefanutti 2011-04-21T16:50:24Z 2011-04-21T16:50:24Z Two things I am thinking. I have to analyze them better, but for sure you can help me before I'll find the answer myself. The first thing is that maps are usually represented using the graphs without considering multiple edges, which is good for coloring but I am not sure abount counting. For example, considering multiple edges the dual graph wouldn't have triangular faces. The second thing is about reversibility: do all triangulations have duals 3-regular planar graphs? ![maps and triangulations](<a href="http://4coloring.files.wordpress.com/2011/04/counting-maps-duals-and-triangulations-v2.png" rel="nofollow">4coloring.files.wordpress.com/2011/04/&hellip;</a>) http://mathoverflow.net/questions/62328/is-there-a-formula-to-count-how-many-different-topological-regular-maps-can-be-cr/62336#62336 Comment by Mario Stefanutti Mario Stefanutti 2011-04-21T07:16:14Z 2011-04-21T07:16:14Z I made a correction to the question (as pointed out by jc). I was interested in &quot;regular maps&quot; without forcing 3-vertex-connectivity. Sorry for the mistake. The abstract of the paper reports: &quot;In the paper, we enumerate three classes of cubic planar maps with no loops or multiple edges: 1-connected; 2-connected; 3-connected and triangle-free.&quot; The results I found manually give these results for 3, 4 and 5 faces: 1 maps, 3 maps, 20 maps. http://mathoverflow.net/questions/62328/is-there-a-formula-to-count-how-many-different-topological-regular-maps-can-be-cr Comment by Mario Stefanutti Mario Stefanutti 2011-04-19T22:32:17Z 2011-04-19T22:32:17Z Yes, you are correct. My mistake. I want to consider only &quot;regular maps&quot; without forcing 3-vertex-connectivity. Only vertexes having 3 edges. For example in the next picture, starting from a map of four faces (3 + the ocean) and adding one face, I would like to count maps excluding those generated from symmetries. <a href="http://4coloring.files.wordpress.com/2011/04/counting-maps-example.png" rel="nofollow">4coloring.files.wordpress.com/2011/04/&hellip;</a> I'll remove 3-connected from the question. http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph/61285#61285 Comment by Mario Stefanutti Mario Stefanutti 2011-04-12T15:07:24Z 2011-04-12T15:07:24Z Printed. I'm not that expert but I'll try to read it. Thanks! http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph/61233#61233 Comment by Mario Stefanutti Mario Stefanutti 2011-04-12T15:06:10Z 2011-04-12T15:06:10Z Thanks for the answer. I inserted a note to comment made by &quot;Thierry Zell&quot;. It applies also to this comment. Thanks again. http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph Comment by Mario Stefanutti Mario Stefanutti 2011-04-12T15:02:55Z 2011-04-12T15:02:55Z @all: Thanks for the info. Yes, it is the problem I'm facing. But to get the &quot;number of colorings&quot; the only method I found is to compute the chromatic polynomial, which is known only for few graphs and it is hard to find for more complex cases. Do you know of papers that directly approach the computation of the &quot;number of colorings without exchanges of colors&quot;? I've implemented a brute force algorithm to color a given map with four colors. I'll try to extend it to find all possible colorings manually ... excluding exchanges. <a href="http://www.youtube.com/user/mariostefanutti#p/u/2/YmYGFxtj2es" rel="nofollow">youtube.com/user/mariostefanutti#p/u/2/&hellip;</a>