Naslov
Combinatorial cube packings in the cube and the torus

Autori
Dutour Sikirić, Mathieu ; Itoh, Yoshiaki

Izvornik
European journal of combinatorics (0195-6698) 31 (2010); 517-534

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
asymptotic ; packing density ; extremal problem

Sažetak
We consider sequential random packing of cubes z+[0, 1]^n with z in (1/N)Z^n into the cube [0, 2]^n and the torus R^n/2Z^n as N goes to infinity. In the cube case [0, 2]^n as N goes to infinity the random cube packings thus obtained are reduced to a single cube with probability 1-O(1/N). In the torus case the situation is different: for n<=2, sequential random cube packing yields cube tilings, but for n>=3 with strictly positive probability, one obtains non-extensible cube packings. So, we introduce the notion of combinatorial cube packing, which instead of depending on N depend on some parameters. We use use them to derive an expansion of the packing density in powers of 1/N. The explicit computation is done in the cube case. In the torus case, the situation is more complicate and we restrict ourselves to the case N equal to infinity of strictly positive probability. We prove the following results for torus combinatorial cube packings: (i) We give a general Cartesian product construction. (ii) We prove that the number of parameters is at least n(n+1)/2}; ; ; ; ; ; ; ; ; ; and we conjecture it to be at most 2^n-1. (iii) We prove that cube packings with at least 2^n-3 cubes are extensible. (iv) We find the minimal number of cubes in non-extensible cube packings for n odd and n<=6.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA