On the Number of Hamiltonian Cycles in a Boolean Cube
In the authors' words
It is shown that, as , the logarithm of the number of decompositions into cycles of the -dimensional Boolean cube is \[ 2^n(\ln n-1+o(1)), \] and the logarithm of the number of Hamiltonian cycles in is at least \[ 2^{n-1}(\ln n-1+o(1)). \] It is proved that, in , every perfect matching whose edges belong to at most directions can be extended to a Hamiltonian cycle for every .
Appeared: Friday, October 9. arXiv. Preprint with a published version.
Published version: Diskretn. Anal. Issled. Oper., Ser. 1, 8:2 (2001), 52-62
Authors' comment: This article was published in Russian in 2001. The results of this article have been surpassed by the following papers. 1.Feder T., Subi C., Nearly tight bounds on the number of Hamiltonian circuits... Inf. Process. Lett. 109, No. 5, 267-27