[Go to site: main page, start]
TOPICS
Search

Keller's Conjecture

Keller's conjecture states that every tiling of R^n by translates of the unit hypercube contains two hypercubes that share a complete (n-1)-dimensional face. The conjecture generalizes Minkowski's conjecture.

Perron (1940) proved Keller's conjecture in dimensions six and less. To study the remaining dimensions, Corrádi and Szabó (1990) translated the tiling problem into graph theory using the generalized Keller graphs G_(n,s). A clique of size 2^n in G_(n,s) encodes a face-sharing-free tiling of n-dimensional space and therefore a counterexample to Keller's conjecture in that dimension. Such a counterexample also gives counterexamples in every higher dimension. The ordinary n-dimensional Keller graph G_n is G_(n,2).

Using this graph formulation, Lagarias and Shor (1992) disproved Keller's conjecture in dimensions 10 and higher, and Mackey (2002) disproved it in dimensions eight and higher. Debroni et al. (2011) showed that the clique number of G_(7,2) is 124. This ruled out counterexamples whose hypercube coordinates are integers or half-integers, but did not settle the unrestricted seven-dimensional case.

The remaining case was subsequently reduced to ruling out a clique of size 128 in G_(7,3), G_(7,4), and G_(7,6). Brakensiek et al. (2022) encoded the clique search as a satisfiability problem and used symmetry breaking to prove that none of the three graphs contains such a clique. Keller's conjecture is therefore true in dimensions one through six by Perron (1940) and in dimension seven by Brakensiek et al. (2022), but false in dimension eight by Mackey (2002) and consequently in every higher dimension.

See also

Generalized Keller Graph, Hypercube, Keller Graph, Minkowski's Conjecture

Explore with Wolfram|Alpha

References

Brakensiek, J.; Heule, M. J. H.; Mackey, J.; and Narváez, D. E. "The Resolution of Keller's Conjecture." J. Automated Reasoning 66, 277-300, 2022. https://doi.org/10.1007/s10817-022-09623-5.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.; Myrvold, W.; Shor, P.; and Weerapurage, D. "A Complete Resolution of the Keller Maximum Clique Problem." In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (Ed. D. Randall). Philadelphia, PA: SIAM, pp. 129-135, 2011. https://doi.org/10.1137/1.9781611973082.11.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 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." https://math.mit.edu/~shor/lecture_notes.pdf.

Referenced on Wolfram|Alpha

Keller's Conjecture

Cite this as:

Weisstein, Eric W. "Keller's Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KellersConjecture.html

Subject classifications