Geodesic
On the number of partitions of the hypercube ${\mathbf Z}_q^n$ into large subcubes
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 2, pp. 1503-1521 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, subcube, star pattern, associative block design, SAT, $k$-SAT.
Mots-clés : partition, partition of hypercube, star matrix, fractal matrix 
@article{SEMR_2024_21_2_a29,
     author = {Yu. V. Tarannikov},
     title = {On the number of partitions of the hypercube ${\mathbf Z}_q^n$ into large subcubes},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1503--1521},
     year = {2024},
     volume = {21},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a29/}
}
TY  - JOUR
AU  - Yu. V. Tarannikov
TI  - On the number of partitions of the hypercube ${\mathbf Z}_q^n$ into large subcubes
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 1503
EP  - 1521
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a29/
LA  - ru
ID  - SEMR_2024_21_2_a29
ER  - 
%0 Journal Article
%A Yu. V. Tarannikov
%T On the number of partitions of the hypercube ${\mathbf Z}_q^n$ into large subcubes
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 1503-1521
%V 21
%N 2
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a29/
%G ru
%F SEMR_2024_21_2_a29
Yu. V. Tarannikov. On the number of partitions of the hypercube ${\mathbf Z}_q^n$ into large subcubes. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 2, pp. 1503-1521. http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a29/

[1] N. Alon, J. Balogh, V.N. Potapov, “Partitioning the hypercube into smaller hypercubes”, Illinois J. Math., 68:4 (2024), arXiv: 2401.00299v3 | DOI

[2] Y. Filmus, E.A. Hirsch, S. Kurz, F. Ihringer, A. Riazanov, A.V. Smal, M. Vinuals, “Irreducible subcube partitions”, Electron. J. Comb., 30:3 (2023), P3yu29 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v30i3p29/pdf

[3] V.N. Potapov, “Clique matchings in the $k$-ary $n$-dimensional cube”, Sib. Math. J., 52:2 (2011), 303–310 | DOI | Zbl

[4] V.N. Potapov, “On the multidimensional permanent and $q$-ary designs”, Sib. Èlectron. Mat. Izv., 11 (2014), 451–456 | Zbl

[5] Yu.V. Tarannikov, “On the existence of Agievich-primitive partitions”, J. Appl. Ind. Math., 16:4 (2022), 809–820 | DOI | Zbl

[6] S. Agievich, “Bent rectangles”, Boolean functions in cryptology and information security, Selected papers based on the presentations at the NATO-Russia Advanced Study Institute on Boolean functions in cryptology and information security (Zvenigorod, Russia, September 8-18, 2007), eds. P. Bart et al., IOS Press, Amsterdam, 2008, 3–22 | DOI | Zbl

[7] R.L. Rivest, “On hash-coding algorithms for partial-match retrieval”, Proceedings of the 15th Annual Symposium on Switching and Automata Theory (October), 1974, 95–103 | DOI

[8] A.E. Brouwer, “On associative block designs”, Combinatorics (Keszthely 1976), Colloq. Math. Soc. Janos Bolyai, 18, 1978, 173–184 | Zbl

[9] J.H. van Lint, “$\{0,1,*\}$-distance problems in combinatorics”, Surveys in combinatorics 1985, Pap. 10th Br. Combin. Conf. (Glasgow/Scotl., 1985), Lond. Math. Soc. Lect. Note Ser., 103, eds. I. Anderson, Cambridge University Press, Cambridge, 1985, 113–135 | Zbl

[10] J.H. van Lint, R.M. Wilson, A course in combinatorics, 2nd Edition, Cambridge University Press, Cambridge, 2001 | DOI | Zbl

[11] J.A. La Poutré, “A theorem on associative block designs”, Discrete Math., 58 (1986), 205–208 | DOI | Zbl

[12] V.N. Potapov, “DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces”, Electron. J. Comb., 29:3 (2022), P3.37 | DOI | Zbl