Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Fix one edge $e$ of the graph (1-skeleton) of an icosahedron. By a computer search, I found that there are 1024 Hamiltonian cycles that include $e$. [But see edit below re directed vs. undirected!] With the two endpoints of $e$ fixed, there are 10 "free" vertices in the cycle. Because $1024=2^{10}$, it makes me wonder if there might be a combinatorial viewpoint that makes it evident that there are 1024 cycles including a fixed edge. It could just be a numerical coincidence, but if anyone sees an idea for an argument, I'd appreciate hearing it. Thanks!
icosahedral graph
Incidentally, this MathWorld page says there are 2560 Hamiltonian cycles all together (without the fixed edge condition). (Thanks to Kristal Cantwell for pointing me to this page.)

Edit. I apologize for misleading! :-/ When I looked at the full output of paths more carefully, I realize I inadvertently computed directed cycles, so each is represented twice, i.e., both $$ \lbrace 2, 7, 6, 11, 8, 9, 4, 10, 12, 5, 3, 1 \rbrace $$ $$ \lbrace 1, 3, 5, 12, 10, 4, 9, 8, 11, 6, 7, 2 \rbrace $$ are included, etc. So there are 512 undirected cycles, 1024 directed cycles. The paths are listed here: hpaths.html.

share|improve this question
7  
Joe, at least indeed 1024 x 30 / 12 = 2560. (Every edge belongs to 2/5 of all H. C. s) –  Gil Kalai Sep 5 '10 at 12:31
2  
As 2560 is not a multiple of 3, then there must be a Hamiltonian cycle with three-fold rotational symmetry. –  Robin Chapman Sep 5 '10 at 12:53
2  
But there are also 12-2=10 triangles on each side of the cycle. This may incite to count pairs of triangulated 12-gons (without interior vertices) which "match up" to an icosahedron. Triangulated 12-gons are counted by the 10-th Catalan number, but there are far less triangulations with at most 4 triangles at each vertex, which is obviously necessary (and maybe sufficient) to have an icosahedral "complement". Translated in terms of binary trees, this amounts to a limitation to depth at most 4 trees, or up/right paths between the diagonal and some (3rd?) subdiagonal in a 10x10 square... –  BS. Sep 5 '10 at 14:06
    
@Gil: Nice!! @Robin: Sorry to be slow---Could you expand on your logic a bit? @BS: That seems a promising approach! –  Joseph O'Rourke Sep 5 '10 at 14:17
3  
To expand on Robin's comment, the group of rotational symmetries of the icosahedron has elements of order 3. If you consider the action of one such element on the set of Hamiltonian cycles, there must be a fixed point, otherwise the orbits would all have size 3 and so the whole set would have size a multiple of 3. –  Colin Reid Sep 5 '10 at 17:01

1 Answer 1

up vote 13 down vote accepted

I've fed these Hamiltonian cycles into Brendan McKay's NAUTY software. They fall into the following isomorphic collections:

  • 6 asymmetric collections, with 48 examples of each
  • 3 collections with a rotational symmetry, with 24 examples of each
  • 5 collections with a reflectional symmetry, with 24 examples of each
  • 2 collections with two reflectional symmetries, with 12 examples of each
  • 1 collection with six-fold rotational symmetry, with 8 examples.

It makes some sense that an asymmetric cycle will have 48 examples: the specified link can be any of the 12 links, in either direction, and there is a two-fold symmetry in the graph once one directed link has been selected. This gives the correct total (using undirected counts):

   6×48 + 3×24 + 5×24 + 2×12 + 1×8 = 512

See below for a picture of the last type, by the way. This uses the same vertex numbers as in the original question. From the picture, you can believe that there are two isomorphic classes of vertex, outer and inner -- different, for example, in that each outer vertex is connected to the next outer vertex in the cycle. All links are between an outer and an inner vertex, but there are two isomorphic classes, and the cycle alternates between them, ABABABABABAB. (You can see that they are different by comparing the result of ABA and BAB -- specifically, whether the end is connected to the start.)

icosahedron_hamiltonians_hexagonal_5a9fd25

I have images of the other symmetrical cycles.

Anyway, the point is that only one of the types has 3-fold symmetry -- as Robin pointed out, there must be at least one for the total to be indivisible by 3. But with only one, it will prove impossible to partition the collections into two groups of 256. This looks like bad news for a base-2 explanation of 512.

share|improve this answer
    
@ed: Thanks for your careful investigation! And for the link to nauty, which is new to me. Alas, I agree it does not look promising for an explanation of $2^9$. Beautiful images, incidentally! –  Joseph O'Rourke Jan 17 '11 at 1:28

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.