Discrete mathematics and mathematical cybernetics

On the number of partitions of the hypercube ${\mathbf Z}_q^n$ into large subcubes

Yu. V. Tarannikov<sup>ab

a</sup> Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
^b Mech. & Math. Department, Lomonosov Moscow State University, 119992, Moscow, Russia

Abstract: We prove that the number of partitions of the hypercube ${\mathbf Z}_q^n$ into $q^m$ subcubes of dimension $n-m$ each for fixed $q$, $m$ and growing $n$ is asymptotically equal to $n^{(q^m-1)/(q-1)}$.
For the proof, we introduce the operation of the bang of a star matrix and demonstrate that any star matrix, except for a fractal, is expandable under some bang, whereas a fractal remains to be a fractal under any bang.

Keywords: combinatorics, enumeration, asymptotics, partition, partition of hypercube, subcube, star pattern, star matrix, fractal matrix, associative block design, SAT, $k$-SAT.

UDC: 519.115.5

MSC: 05A18

Received November 5, 2024, published December 31, 2024

DOI: 10.33048/semi.2024.21.096