Decomposing the even hypercube $Q_n$ into $2^m n$-cycles in the unresolved window of the regime $n < 2^m < 2^n/n$

For even $n$, the $n$-dimensional hypercube $Q_n$ has $n2^{n-1}$ edges, and a decomposition of $Q_n$ into cycles of common length $2^m n$ is possible only when $2^m n$ divides the edge count and $2^m n$ is at most the number $2^n$ of vertices, i.e. $2^m < 2^n/n$. Tapadia, Waphare and Borse (2018) constructed such decompositions whenever $n \ge 2^m$ and asked whether they exist for $n < 2^m$. Axenovich, Offner and Tompkins (2021) later resolved most of that range, so the surviving open core is an explicitly identifiable infinite family of instances: writing $n = 2^{\alpha}u$ with $u$ odd, $i_1 = \lfloor \log_2 u \rfloor$ and $j$ the number of 1s in the binary expansion of $u$, the open pairs are exactly those with $2^{n-i_1-j+1-\alpha} < 2^m < 2^n/n$, beginning with a decomposition of $Q_{14}$ into $7 \cdot 2^{11}$-cycles. The problem asks for a construction covering every such pair, or a proof of impossibility for the failing pairs.

Background

The $n$-dimensional hypercube $Q_n$ is the graph whose $2^n$ vertices are the binary strings of length $n$, two vertices being adjacent when they differ in exactly one coordinate; it is $n$-regular with $n2^{n-1}$ edges and bipartite, so it contains no odd cycles. A decomposition of a graph is a partition of its edge set into edge-disjoint subgraphs; when all parts are cycles with the same number $k$ of edges (a $k$-cycle), one speaks of a $k$-cycle decomposition. Since a cycle cannot repeat vertices, a cycle in $Q_n$ has length at most $2^n$, and any cycle decomposition of $Q_n$ needs the cycle length to divide $n2^{n-1}$. For target lengths of the form $2^m n$ with $n$ even, divisibility is automatic whenever $m \le n-1$, so the binding feasibility condition is $2^m n \le 2^n$, i.e. $2^m \le 2^n/n$. Edge decompositions of hypercubes are studied both intrinsically and because of interconnection networks for parallel computing, where families of edge-disjoint long cycles support fault-tolerant and adaptive routing.

Several classical cases are settled: $Q_n$ admits a decomposition into Hamiltonian cycles (cycles through all $2^n$ vertices) for every even $n \ge 2$; El-Zanati and Vanden Eynden proved that $Q_n$ decomposes into $2^l$-cycles for all $2 \le l \le n$; and Ramras, Mollard and others studied highly symmetric decompositions. Ramras introduced the notion of a fundamental set: a subset $F$ of $E(Q_n)$ is fundamental for $Q_n$ with respect to a subgroup $\mathcal{G}$ of the automorphism group of $Q_n$ if the translates of $F$ under $\mathcal{G}$ partition $E(Q_n)$. Mollard and Ramras asked, for which divisors $k$ of $n2^{n-1}$ the cube $Q_n$ has a decomposition into $k$-cycles or into $k$-paths (paths with $k$ edges). Erde (2014) conjectured that for even $n$ every path length $r < 2^n$ dividing $n2^{n-1}$ decomposes $Q_n$ (for odd $n$ the path problem is completely settled: decompositions exist exactly for lengths at most $n$ dividing the edge count). Ramras conjectured that for every even $n \ge 4$ the edge set of a path of length $2n$ is a fundamental set of $Q_n$.

Tapadia, Waphare and Borse proved that for even $n$ and $m \ge 1$ with $n \ge 2^m$, the hypercube $Q_n$ has a decomposition into $2^m n$-cycles; in fact their Theorem 1.4 provides decompositions with an additional perfect-matching property: each cycle carries a designated set of $2^m$ edges such that the union of the designated edges over all cycles of the decomposition is a perfect matching of $Q_n$ (a set of edges covering every vertex exactly once). From these they derived path decompositions of $Q_n$ into paths of lengths $n, 2n, \ldots, 2^{m-1}n$, solving special cases of Erde's conjecture and making partial progress on Ramras's. They explicitly state that the problem remains open for $n < 2^m$.

The decisive subsequent progress is due to Axenovich, Offner and Tompkins. Their main theorem states: write $n = x y 2^{\alpha}$ with $x, y \ge 1$ odd and $\alpha \ge 1$, and write the binary expansion of $y$ as $y = 2^{i_1} + 2^{i_2} + \cdots + 2^{i_j}$ with $i_1 > i_2 > \cdots > i_j = 0$; then for every $q$ with $0 \le q \le n - i_1 - 2xj$, the cube $Q_n$ has a decomposition into cycles of length $y 2^{n-i_1-j+1-q}$. A stated corollary is that $Q_n$ decomposes into $n 2^m$-cycles whenever $2n \le n2^m \le 2^n/n$, and they also prove that $Q_n$ decomposes into paths of every length $\ell \le 2^n/n$ dividing $n2^{n-1}$, settling Erde's conjecture up to a linear factor. Specializing their theorem to $y = u$, the odd part of $n$ (that is, $x = 1$), shows that $n 2^m$-cycle decompositions exist for all $2^m \le 2^{\,n-i_1-j+1-\alpha}$: this resolves most of the range Tapadia et al. left open, including for instance $Q_6$ into 48-cycles and $Q_8$ into 128-cycles. The authors state that it remains open which cycle lengths between $2^{n+1}/n$ and $2^n$ decompose $Q_n$, and that their methods cannot construct, for example, a decomposition of $Q_{14}$ into $7 \cdot 2^{11}$-cycles. They also note that even a full resolution of the cycle problem would not finish Erde's conjecture, since paths of length greater than $2^{n-1}$ cannot be obtained by splitting cycles.

Problem Statement

For an even integer $n \ge 4$, write $n = 2^{\alpha} u$ with $u$ odd, let $i_1 = \lfloor \log_2 u \rfloor$, and let $j$ be the number of 1s in the binary expansion of $u$. Determine for every integer $m \ge 1$ with

$2^{\,n-i_1-j+1-\alpha} < 2^m < 2^n/n$

whether the edge set of the hypercube $Q_n$ admits a decomposition into cycles each of length $2^m n$. These are exactly the instances of the question of Tapadia, Waphare and Borse (who settled $n \ge 2^m$) in the regime $n < 2^m$ that remain open after the constructions of Axenovich, Offner and Tompkins; both bounds are necessary feasibility limits, since a decomposition requires $2^m n$ to divide $n2^{n-1}$ and $2^m n \le 2^n$, and the upper endpoint $2^m n = 2^n$ is the classically known Hamiltonian case. The window is nonempty precisely when $j \ge 3$; the smallest instance is a decomposition of $Q_{14}$ into $7 \cdot 2^{11}$-cycles ($m = 10$), followed by $Q_{22}$ into $11 \cdot 2^{18}$-cycles, $Q_{26}$ into $13 \cdot 2^{22}$-cycles, $Q_{28}$ into $7 \cdot 2^{25}$-cycles, $Q_{30}$ into $15 \cdot 2^{25}$- and $15 \cdot 2^{26}$-cycles, and the infinite family $n = 2(2^k - 1)$, $k \ge 3$, which contributes exactly $k-2$ instances each. The objective concerns every pair $(n, m)$ in this window; the analogous path and mixed path-cycle decomposition variants are separate questions. The related but distinct open questions — Erde's conjecture for path lengths above $2^n/n$ and Ramras's fundamental-set conjecture for paths of length $2n$ — remain context for, rather than part of, this question.

References

1. S. A. Tapadia, B. N. Waphare, Y. M. Borse, Decompositions of $n$-Cube into $2^mn$-Cycles, arXiv:1804.01243 (2018). https://arxiv.org/abs/1804.01243
2. J. Erde, Decomposing the cube into paths, Discrete Mathematics 336 (2014) 41-45, doi:10.1016/j.disc.2014.07.019. https://doi.org/10.1016/j.disc.2014.07.019
3. M. Axenovich, D. Offner, C. Tompkins, Long path and cycle decompositions of even hypercubes, European Journal of Combinatorics 95 (2021) 103320, doi:10.1016/j.ejc.2021.103320 (preprint arXiv:1905.10114). https://doi.org/10.1016/j.ejc.2021.103320
4. M. Mollard, M. Ramras, Edge decompositions of hypercubes by paths and by cycles, Graphs and Combinatorics 31 (2015) 729-741, doi:10.1007/s00373-013-1402-0. https://doi.org/10.1007/s00373-013-1402-0
5. M. Ramras, Fundamental subsets of edges of hypercubes, Ars Combinatoria 46 (1997) 3-24. https://dblp.org/rec/journals/arscom/Ramras97.html
6. S. El-Zanati, C. Vanden Eynden, Cycle factorizations of cycle products, Discrete Mathematics 189 (1998) 267-275, doi:10.1016/S0012-365X(98)00053-3. https://doi.org/10.1016/S0012-365X(98)00053-3
7. D. Anick, M. Ramras, Edge Decompositions of Hypercubes by Paths, arXiv:1308.4949 (2013). https://arxiv.org/abs/1308.4949
8. S. Gibson, D. Offner, Decompositions of even hypercubes into cycles whose length is a power of 2, Involve, a Journal of Mathematics 17 (2024) 233-247, doi:10.2140/involve.2024.17.233. https://doi.org/10.2140/involve.2024.17.233
9. D. Saranya, S. Jeevadoss, V. Nalini, V. Chitra, Decomposition of hypercube graphs into paths and cycles having k edges, AKCE International Journal of Graphs and Combinatorics 22 (2) (2025) 190-195, doi:10.1080/09728600.2024.2444564. https://doi.org/10.1080/09728600.2024.2444564
10. S. A. Tapadia, B. N. Waphare, Decomposing hypercubes into cycles: an approach to the Oberwolfach problem, Journal of Combinatorial Mathematics and Combinatorial Computing 128 (2025) 31-50, doi:10.61091/jcmcc128-02. https://doi.org/10.61091/jcmcc128-02
11. M. Aberle, S. Gold, R. Moshe, D. Offner, Cycle decompositions of cartesian products of two cycles, arXiv:2310.13493 (2023); journal version doi:10.1007/s00373-025-02953-2. https://arxiv.org/abs/2310.13493