Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations

It has been shown that for every perfect matching M of the d-dimensional n-vertex hypercube, d⩾2, n=d2, there exists a second perfect matching M′ such that the union of M and M′ forms a Hamiltonian circuit of the d-dimensional hypercube. We prove a generalization of a special case of this result when there are two dimensions that do not get used by M. It is known that the number Md of perfect matchings of the d-dimensional hypercube satisfies and, in particular, (2d/n)n/2(n/2)!⩽Md⩽(d!)n/(2d). It has also been shown that the number Hd of Hamiltonian circuits of the hypercube satisfies 1⩽limd→∞(logHd)/(logMd)⩽2. We finally strengthen this result to a nearly tight bound ((dlog2/(eloglogd))(1−on(1)))⩽Hd⩽(d!)n/(2d)((d−1)!)n/(2(d−1))/2 proving that limd→∞(logHd)/(logMd)=2. This means that the bound Hd⩾Md is improved to a nearly tight , so the number of Hamiltonian circuits in the hypercube is nearly quadratic in the number of perfect matchings. The proofs are based on a result for graphs that are the Cartesian product of squares and arbitrary bipartite regular graphs that have a Hamiltonian cycle. We also study a labeling scheme related to matchings.