PreprintarXiv licencearXiv
On the Number of Hamiltonian Cycles in a Boolean Cube
Abstract
It is shown that, as n→∞, the logarithm of the number of decompositions into cycles of the n-dimensional Boolean cube En is 2n(ln n−1+o(1)), and the logarithm of the number of Hamiltonian cycles in En is at least 2n−1(ln n−1+o(1)). It is proved that, in En, every perfect matching whose edges belong to at most k directions can be extended to a Hamiltonian cycle for every n≥ n0(k).
Related
- On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
- The maximum number of Hamiltonian cycles in tournaments
- An m2.943 Bohnenblust--Hille Bound on the Boolean Cube
- Additive energy, Freiman's lemma, and an edge-isoperimetric problem on the boolean cube
- Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
BibTeX
@misc{perezhogin2026number,
title = {{On the Number of Hamiltonian Cycles in a Boolean Cube}},
author = {A. L. Perezhogin and V. N. Potapov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11941},
eprint = {2610.11941},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11941},
}
RIS
TY - UNPB
TI - On the Number of Hamiltonian Cycles in a Boolean Cube
AU - A. L. Perezhogin
AU - V. N. Potapov
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11941
UR - https://arxiv.org/abs/2610.11941
AB - It is shown that, as n→∞, the logarithm of the number of decompositions into cycles of the n-dimensional Boolean cube E^n is 2^n(ln n−1+o(1)), and the logarithm of the number of Hamiltonian cycles in E^n is at least 2^n−1(ln n−1+o(1)). It is proved that, in E^n, every perfect matching whose edges belong to at most k directions can be extended to a Hamiltonian cycle for every n≥ n_0(k).
ER -