Hypercube partitions and matchings counting
Problem 1.1 · arXiv:2401.00299
Status open medium confidence
Problem 1.1 asks to determine or estimate four functions: m(d) (perfect matchings of Q_d), m'(d) (all matchings), f(d) (partitions into subhypercubes), and f_{\leq 2}(d) (a restricted variant introduced by the authors). The source paper itself establishes that the asymptotic order of f(d) is not much larger than m(d), providing bounds but leaving precise determination of all four functions open. A potentially related November 2024 preprint (arXiv:2411.04479) proves asymptotic counts for partitions of the q-ary hypercube Z_q^n into subcubes of fixed dimension, which for q=2 may address special cases of f(d), but it does not appear to directly cite or fully resolve Problem 1.1.
Reviewer notes. The source paper was published in Illinois Journal of Mathematics, Vol. 69, Issue 1 (April 2025). Problem (iii) on f(d) was originally raised by Gadouleau at the 29th British Combinatorial Conference in 2022. A related paper arXiv:2411.04479 ('On the number of partitions of the hypercube Z_q^n into large subcubes', November 2024) proves that for fixed q and m the count of partitions of Z_q^n into q^m subcubes of dimension n-m is asymptotically n^{(q^m-1)/(q-1)}; for q=2 this covers partitions where all parts have the same fixed dimension, a special case of f(d). However, the WebFetch response was ambiguous and could not confirm authors, a direct citation of 2401.00299, or coverage of m(d), m'(d), or f_{leq2}(d). No other confirmed follow-up resolving the full problem was found.
Context
$Q_d := \{0,1\}^d$ is the $d$-dimensional hypercube; $f(d)$ counts partitions of its vertex set into subhypercubes; $m(d)$ and $m^{\prime}(d)$ count perfect matchings and all matchings respectively. Problem (iii) was originally raised by Gadouleau at the 29th British Combinatorial Conference in 2022; problem (iv) is introduced by the authors as a closely related variant.
Notes. Part (iii) attributed to Gadouleau (2022, unpublished talk); parts (i), (ii), (iv) are the authors' own formulations.
Source paper
Partitioning the hypercube into smaller hypercubes
Noga Alon, Jozsef Balogh, Vladimir N. Potapov · 2024-11-07
https://arxiv.org/abs/2401.00299