О числе разбиений гиперкуба Z_q^n на большие подкубы

О числе разбиений гиперкуба ${\bf Z}_q^n$ на большие подкубы

Таранников Ю. В.

УДК 519.115.5 
DOI: 10.33048/semi.2024.21.096  
MSC 05A18


Аннотация:

We prove that the number of partitions of the hypercu\-be ${\bf 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.

 

Ключевые слова: combinatorics, enumeration, asymptotics, partition, partition of hypercube, subcube, star pattern, star matrix, fractal matrix, associative block design, SAT, $k$-SAT.