Keller conjectured that tiling an -dimensional space with -dimensional hypercubes of equal
size yields an arrangement in which at least two hypercubes have an entire -dimensional "side" in common. This conjecture
generalizes Minkowski's conjecture.
Corrádi and Szabó (1990) reformulated the conjecture by showing that if there exists a clique of size (the largest possible) in the class of graphs which have
now become known as Keller graphs, then Keller's
conjecture is false in that dimension. However, note that the nonexistence
of such a clique does not necessarily imply the truth of the conjecture, only
that no counterexample exists with hypercubes whose coordinates are integers or half-integers
(Debroni et al. 2011).
Perron (1940) proved Keller's conjecture to be true in dimensions six and less, and it has been shown to be false in dimensions 8, 10, and 12 by Lagarias and Shor (1992),
who found a cliques of size and in the 10-and 12-dimensional Keller
graphs, respectively, and by Mackey (2002), who found a clique of size in the Keller graph of dimension
eight. Debroni et al. (2011) recently showed the clique
number of the 7-dimensional Keller graph is 124,
thus suggesting (but not establishing) that Keller's conjecture is false in that
dimension.
Cipra, B. "If You Can't See It, Don't Believe It." Science259, 26-27, 1993.Cipra, B. What's
Happening in the Mathematical Sciences, Vol. 1. Providence, RI: Amer.
Math. Soc., p. 24, 1993.Corrádi, K. and Szabó, S.
"A Combinatorial Approach for Keller's Conjecture." Periodica Mathematica
Hungarica. Journal of the János Bolyai Math. Soc.21, 95-100, 1990.Debroni,
J.; Eblen, J. D.; Langston, M. A.; Shor, P.; Myrvold, W.; and Weerapurage,
D. "A Complete Resolution of the Keller Maximum Clique Problem." Proceedings
of the 22nd ACM-SIAM Symposium on Discrete Algorithms. pp. 129-135, 2011.
http://www.siam.org/proceedings/soda/2011/SODA11_011_debronij.pdf.Keller,
O. H. "Über die luckenlose Einfullung des Raumes mit Wurfeln."
J. reine angew. Math.163, 231-248, 1930.Lagarias, J. C.
and Shor, P. W. "Keller's Cube-Tiling Conjecture Is False in High Dimensions."
Bull. Amer. Math. Soc.27, 279-283, 1992.Mackey, J. "A
Cube Tiling of Dimension Eight with No Facesharing." Disc. Comput. Geom.28,
275-279, 2002.Peron, O. "Über lückenlose Ausfüllung
des -dimensionalen
raumes durch kongruente Würfel I & II." Math. Z.46,
1-26 and 161-180, 1940.Shor, P. "Minkowski's and Keller's Cube-Tiling
Conjectures." http://www-math.mit.edu/~shor/lecture_notes.ps.