[seqfan] Re: Number of Hamiltonian cycles in the n-cube

[David Applegate]

Looking at Abbot's paper, at least one error is the claim "it is easy
to verify that (12) implies (3)."

(12) is h(m+3) >= 6^2^m h(m), which implies h(m) >= 6^2^(m-3) for
m >= 4, or h(m) >= 2/5 * (6^2^(m-3)) for m >= 1, but certainly doesn't
imply (3) h(m) >= (7 sqrt(6))^(2^n-4)

-Dave

> From seqfan-bounces at list.seqfan.eu Thu Dec  6 18:21:13 2012
> Date: Thu, 6 Dec 2012 18:21:00 -0500
> From: Charles Greathouse <charles.greathouse at case.edu>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Subject: [seqfan] Number of Hamiltonian cycles in the n-cube

> Sequence A159344 counts the number of Hamiltonian cycles in the n-cube
> (modding out the full automorphism group). This sequence was brought
> to my attention by the recent work of Haanpaa & Ostergard who in a
> computational tour de force discover a(6).

> The sequence contains a lower bound due to Abbott 1966, which is available here:
> http://math.ca/10.4153/CMB-1966-068-6

> a(n) is, in Abbott's terminology, h*(n); see (2) and (3) which yield
> a(n) >= sqrt(294)^(2^n-4)/(n! * 2^n)
> [note that I have written sqrt(294) for 7 sqrt(6)].

> Unfortunately the lower bound seems incompatible with the known values
> of a(n), even for a(3) and a(4) which were known to Abbott. Am I
> misinterpreting the paper? Is there a typographical error? I certainly
> wouldn't want to leave the sequence in its present inconsistent state.

> Charles Greathouse
> Analyst/Programmer
> Case Western Reserve University

> _______________________________________________

> Seqfan Mailing list - http://list.seqfan.eu/