RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2024, том 21, выпуск 2, страницы 1503–1521 (Mi semr1759)

Дискретная математика и математическая кибернетика

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

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

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

Аннотация: 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.

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

УДК: 519.115.5

MSC: 05A18

Поступила 5 ноября 2024 г., опубликована 31 декабря 2024 г.

DOI: 10.33048/semi.2024.21.096



© МИАН, 2025