Conference rusure::math

	I think the right generalization of the G(m,n) experience is to
look at group presentations which have 2 generators, a and b. Let c = ab^-1.
Then imagine there is a Hamiltonian cycle, if possible. Each element of any
right coset of <c> will have the *same* colour edge leaving it. So the number
of possible candiates for Hamiltonian cycles is not 2^|G| but 2^|G:<c>|.
Let k = |G:<c>|. For each element g_1*g_2*...*g_k, g_i=a or b, we need to
know whether j(g) is coprime to |<c>|, where j(g) is given by:
	c^j(g) = g^k.

	I claim that iff g exists such that j(g) is coprime to |<c>|, then
G has a Hamiltonian cycle.

	Note that where G = G(m,n), then a & b commute, we only have k+1
candidates for g. It's easy to see that either ab^(k-1) or ba^(k-1) must
yield a suitable j, assuming m&n are not coprime.

	However, doesn't look as if anyone else is interested in this one...

Cheers,
Andrew.

>	I claim that iff g exists such that j(g) is coprime to |<c>|, then
>G has a Hamiltonian cycle.

	This condition may still be difficult to check. However, there is a 
powerful corrolary to the theorem:

	If G is a group presentation with two generators, a & b, satisfying
the following:
		(i) a & b do *not* commute
		(ii) ab^-1 is of prime order in G
then:
	G is Hamiltonian.

	These are relatively simple requirements. Gee, this is nearly
publishable...

I suppose I should start writing up my proofs.
Cheers,
Andrew.

re .1
    
>	However, doesn't look as if anyone else is interested in this one...
    
    I would be if I could understand it but I don't have the background in
    group theory (or pure maths, more generally).
    
    I have a preference for simple problems that you could explain to a 12
    year old in 5 minutes like Fermat's Last Theorem (finally a theorem!),
    the Goldbach Conjecture, the Continuum Hypothesis (maybe a little hard
    for explaining in 5 minutes)... (-:
    
    It has always seemed to me that in order even to contemplate group
    theory you need to learn all sorts of arcane new terms and notation.
    It's a pity really because it seems to have neat applications.

re .2

    I look forward to seeing your work in print.

>    It has always seemed to me that in order even to contemplate group
>    theory you need to learn all sorts of arcane new terms and notation.
>    It's a pity really because it seems to have neat applications.

	I think you're right on both counts. I find the intersection of
group theory & graph theory particularly attractive. Note 1089 contains
a lot of stuff describing group presentations and Cayley diagrams.

>	I look forward to seeing your work in print.

	Long way to go yet! But I've thought of an application of the pigeon-
hole principle which extends the scope of the corollary even further. I have
a long airflight coming up tomorrow, and I hope to clear my thinking up
during that.

Regards,
Andrew

>	I claim that iff g exists such that j(g) is coprime to |<c>|, then
>G has a Hamiltonian cycle.

	This is only true if C = <c> is normal in G. Now that's the case,
for instance, for the non-abelian group of order 21:
	<a,b| a^3, b^-1aba^-1ba^-1, (ab^-1)^7>

	However, "most" groups don't have a cyclic normal subgroup.

	An instructive case is the group presentation:
	<a,b| a^4, b^2, (ab)^3>

	This is IM to the abstract group S4 ( a = (1234), B = (12) for instance)
C is of prime order, 3, but is not normal in S4. The Cayley diagram looks
like an octahedron with the corners bitten off, and is not Hamiltonian
(examine the cosets of C).

Work to do,
Andrew.

	Alas, someone's got there before me. The "Factor Group Theorem" for
Hamiltonian Cayley digraphs targets exactly the case where a group has
a cyclic normal subgroup. Drat. :-)

Regards,
Andrew.