Keller's Conjecture

Keller conjectured that tiling an n-dimensional space with n-dimensional hypercubes of equal size yields an arrangement in which at least two hypercubes have an entire (n-1)-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 2^n (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 2^(10) and 2^(12) in the 10-and 12-dimensional Keller graphs, respectively, and by Mackey (2002), who found a clique of size 2^8 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.

See also

Hypercube, Keller Graph, Minkowski's Conjecture

Explore with Wolfram|Alpha


Cipra, B. "If You Can't See It, Don't Believe It." Science 259, 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., 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 n-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."

Cite this as:

Weisstein, Eric W. "Keller's Conjecture." From MathWorld--A Wolfram Web Resource.

Subject classifications