5
$\begingroup$

Notes:

  • For "regular" I intend maps in which the boundaries form a 3-regular planar graph
  • For "different" I intend maps that cannot be topologically transformed one into another (faces have to be considered unnamed)

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.

This was my best guess, but I already know that it is not correct because full of symmetries, as it can be verified manually.

General formula:

  • $$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) $$

Examples:

  • 4 faces = $$2\sum_{s_1=3}^5 s_1\left(s_1-1\right) $$
  • 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)$$

Here are the first results that can be found manually (excluding symmetries):

  • 2 faces = 0 possible regular map (an island and the ocean) (not to be counted, because not regular)
  • 3 faces = 1 possible regular map (an island with two regions and the ocean) (two islands and the ocean wouldn't be regular)
  • 4 faces = 3 possible regular maps (can be verified adding a face from the previous map)
  • 5 faces = 20 possible regular maps (ERROR: There were duplicates)
  • 6 faces = 329 possible regular maps (ERROR: There were duplicates)
  • ...

These are all maps up to 5 faces (ERROR: contains duplicates):

maps

Image for the comment on "triangulations of the sphere"

And without duplicates:

MODIFIED: 20/Apr/2011 - Removed "3-connected" from the question. See comment below.

MODIFIED: 21/Apr/2011 - Added a picture with all regular maps up to 5 faces

MODIFIED: 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

MODIFIED: 27/Apr/2011 - Manually computed number of different maps of 6 faces = 329, added numerical IDs to the maps

MODIFIED: 29/Apr/2011 - The manual computation of the number of regular maps contains some duplicated (Homeomorphic pairs)

MODIFIED: 29/Apr/2011 - Just to leave things a little more clean (I removed the duplicates ... I hope)

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ I'm not entirely sure what you mean by "3-connected". The example you give with 3 faces is not 3-vertex-connected, as it only has 2 vertices. If you mean 3-edge-connected, I'm only able to draw one such cubic (3-regular) map with 4 faces (the net of a tetrahedron). $\endgroup$
    – j.c.
    Commented Apr 19, 2011 at 21:16
  • $\begingroup$ Yes, you are correct. My mistake. I want to consider only "regular maps" 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. 4coloring.files.wordpress.com/2011/04/counting-maps-example.png I'll remove 3-connected from the question. $\endgroup$
    – Mario Stefanutti
    Commented Apr 19, 2011 at 22:32
  • $\begingroup$ If you dualize (face->vertex, vertex->face) then you get a simplicial map: all faces triangles. So it seems you are looking for a count of the triangulations of a sphere...? $\endgroup$
    – Joseph O'Rourke
    Commented Apr 21, 2011 at 10:56
  • 1
    $\begingroup$ Actually it matches this one: oeis.org/A163138 (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. $\endgroup$
    – Mario Stefanutti
    Commented Apr 27, 2011 at 14:18
  • 2
    $\begingroup$ I'm confused how you're counting maps, or perhaps what you mean by "excluding symmetries". In your diagram of "maps up to 5 faces", I see a few pairs of maps which appear isomorphic to me, for instance, in the maps coming from the top 4 face map, the map in the bottom center, and in the maps coming from the bottom 4 face map, the map in the bottom left. There are some other examples as well, for instance the map which is a net of a tetrahedron plus one region hanging off one of the three petals. $\endgroup$
    – j.c.
    Commented Apr 27, 2011 at 15:11

2 Answers 2

Reset to default
3
$\begingroup$

Take a look at the following two papers which will give you a feel for how these sorts of enumerations are tackled (typically by methods of generating functions), and will also serve as a bit of a guide to the early literature:

Here's a fairly accessible and readable article by Tutte which doesn't cover your case but serves as an introduction to how map enumeration problems have been treated mathematically.

Here's a review by Bender and Richmond which also describes how to solve some more general versions of map enumeration problems. I'm not sure if it covers your case or not, since I haven't quite managed to formalize what you're looking for, but if you read these papers you should have a good shot at figuring out for yourself where you need to look next.

The duals of the maps you are studying are definitely planar triangulations, and I think that since you don't allow loops in your maps that the duals must be 2-(vertex-)connected triangulations. Since you are considering the "ocean" to be distinct from any of the regions in the islands, I believe this gives your triangulations a root vertex. So my gut feeling is that you want to look at 2-connected rooted triangulations (which if I'm not mistaken were treated by Tutte), but I'll leave it to you to check this guess. I'm still confused about the rooting, but I think looking at triangulations is better than in terms of cubic maps - if you think of your maps without taking duals, then some pairs of vertices have multiple edges (the results derived in the paper mentioned by Igor Rivin are precisely where maps with such multiple edges are excluded).

Lastly, (just for fun, perhaps) there is also a large literature in the high-energy physics / field theory community on planar map / planar graph enumeration due to a connection with diagrammatic expansions in integrals over matrix ensembles. For this angle, you might start with this survey by Di Francesco.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The link to the survey at springerlink.com is broken. I'm also unable to find any snapshot saved on the Wayback Machine. $\endgroup$
    – The Amplitwist
    Commented Dec 14, 2022 at 18:21
2
$\begingroup$

Yes, this is known. See the paper http://www.math.uwaterloo.ca/~nwormald/papers/cubicplanar.ps.gz, which is also nicely written and has good references to related work.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I made a correction to the question (as pointed out by jc). I was interested in "regular maps" without forcing 3-vertex-connectivity. Sorry for the mistake. The abstract of the paper reports: "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." The results I found manually give these results for 3, 4 and 5 faces: 1 maps, 3 maps, 20 maps. $\endgroup$
    – Mario Stefanutti
    Commented Apr 21, 2011 at 7:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .