Abstract
A non-empty subset A of X=X 1×⋅⋅⋅×X d is a (proper) box if A=A 1×⋅⋅⋅×A d and A i ⊂X i for each i. Suppose that for each pair of boxes A, B and each i, one can only know which of the three states takes place: A i =B i , A i =X i ∖B i , A i ∉{B i ,X i ∖B i }. Let F and G be two systems of disjoint boxes. Can one decide whether ∪F=∪G? In general, the answer is ‘no’, but as is shown in the paper, it is ‘yes’ if both systems consist of pairwise dichotomous boxes. (Boxes A, B are dichotomous if there is i such that A i =X i ∖B i .) Several criteria that enable to compare such systems are collected. The paper includes also rigidity results, which say what assumptions have to be imposed on F to ensure that ∪F=∪G implies F=G. As an application, the rigidity conjecture for 2-extremal cube tilings of Lagarias and Shor is verified.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon, N., Bohman, T., Holzman, R., Kleitman, D.J.: On partitions of discrete boxes. Discrete Math. 257, 255–258 (2002)
Grytczuk, J., Kisielewicz, A.P., Przesławski, K.: Minimal partitions of a box into boxes. Combinatorica 24, 605–614 (2004)
Kearnes, K.A., Kiss, E.W.: Finite algebras of finite complexity. Discrete Math. 207, 89–135 (1999)
Keller, O.-H.: Über die lückenlose Erfüllung des Raumes Würfeln. J. Reine Angew. Math. 163, 231–248 (1930)
Keller, O.-H.: Ein Satz über die lückenlose Erfüllung des 5- und 6-dimensionalen Raumes mit Würfeln. J. Reine Angew. Math. 177, 61–64 (1937)
Kisielewicz, A.P., Przesławski, K.: Rigidity and the chess board theorem for cube packings; math.CO/0610693 (2006)
Lagarias, J.C., Shor, P.W.: Keller’s cube-tiling conjecture is false in high dimensions. Bull. Am. Math. Soc. 27, 279–287 (1992)
Lagarias, J.C., Shor, P.W.: Cube tilings and nonlinear codes. Discrete Comput. Geom. 11, 359–391 (1994)
Mackey, J.: A cube tiling of dimension eight with no face sharing. Discrete Comput. Geom. 28, 275–279 (2000)
Perron, O.: Über lückenlose Ausfüllung des n-dimensionalen Raumes durch kongruente Würfel I. Math. Z. 46, 1–26 (1940)
Perron, O.: Über lückenlose Ausfüllung des n-dimensionalen Raumes durch kongruente Würfel II. Math. Z. 46, 161–180 (1940)
Steinc, S., Szabó, S.: Algebra and Tiling: Homomorphisms in the Service of Geometry. American Mathematical Association, Washington (1994)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kisielewicz, A.P., Przesławski, K. Polyboxes, Cube Tilings and Rigidity. Discrete Comput Geom 40, 1–30 (2008). https://doi.org/10.1007/s00454-007-9005-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-007-9005-2