From mark.longridge@canrem.com Sat Feb 24 01:13:35 1996
Return-Path:
Received: from itchy.crso.com (itchy.canrem.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18904; Sat, 24 Feb 96 01:13:35 EST
Received: by canrem.com (PCB-UUCP 1.1f)
id 20BD28; Sat, 24 Feb 96 00:58:14 -0500
To: cube-lovers@life.ai.mit.edu
Reply-To: CRSO.Cube@canrem.com
Sender: CRSO.Cube@canrem.com
Subject: Hamiltonian Circuits
From: mark.longridge@canrem.com (Mark Longridge)
Message-Id: <60.1310.5834.0C20BD28@canrem.com>
Date: Sat, 24 Feb 96 00:25:00 -0500
Organization: CRS Online (Toronto, Ontario)
Mike wrote:
> there's a general graph theory conjecture that cayley graphs are
> hamiltonian (i.e. have hamiltonian circuits).
>
> if we take the cayley graph formed by generators
> {F, F', L, L' U, U', R, R', B, B', D, D'}, the conjecture asserts
> that there is a sequence of N quarter turns that visits every
> position exactly once and returns to START.
> (here N = 43252003274489856000 is the order of the group.)
Here's an easy example:
Hamiltonian Circuit for < u2, r2 >
12 elements, 12 moves in group to reach each element
Identity
/ \
1. u2 r2 12.
| |
2. r2 u2 11.
| |
3. u2 r2 10.
| |
4. r2 u2 9.
| |
5. u2 r2 8.
| |
6. r2 u2 7.
\ /
Antipode
Position at 6. is the antipode
Position at 12. is the identity
Also, I seem to remember that the slice-squared group had 8 elements,
and if you graphed a route through the elements it formed a cube.
After drawing such a graph it is not hard to find a hamiltonian
circuit (using the edges of the cube as a pathway).
This may be true in general for all the platonic solids.
(I need to re-check "Regular Polytopes" by Coxeter).
So we have 2 examples and no counter-examples of the general graph
theory Mike mentions.
-> Mark <-