Talk:Keller's conjecture

Keller's conjecture has been listed as one of the Mathematics good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it.
Review: March 31, 2021. (Reviewed version).

A fact from Keller's conjecture appeared on Wikipedia's Main Page in the Did you know column on 25 April 2021 (check views). The text of the entry was as follows:

Did you know... that a mathematical conjecture about tiling space by cubes was transformed into a problem in graph theory that became a benchmark for clique-finding algorithms?

A record of the entry may be seen at Wikipedia:Recent additions/2021/April. The nomination discussion and review may be seen at Template:Did you know nominations/Keller's conjecture.

Wikipedia

Still an open question?[edit]

Is it still open? Somebody posted the following links to Russian page on open problems, claiming that the conjecture was eventually proved in dimension 7 as well:

Debroni J. A complete resolution of the Keller maximum clique problem / J. Debroni, J. D. Eblen, M. A. Langston, W. Myrvold, P. Shor, D. Weerapurage // Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, California, USA, January 23–25, 2011) / Edited by D. Randall. http://www.siam.org/proceedings/soda/2011/SODA11_011_debronij.pdf
Debroni J. The End to the Keller Conjecture / J. Debroni, J. D. Eblen, M. A. Langston, W. Myrvold, P. Shor, D. Weerapurage // Forty-First Southeastern International Conference on Combinatorics, Graph Theory, and Computing (March 8-12, 2010). http://math.fau.edu/cgtc/cgtc41/Abstracts/WMyrvold.pdf

Maxal (talk) 23:53, 17 April 2013 (UTC)[reply]

Our article states "Although this graph-theoretic version of the conjecture is now resolved for all dimensions, Keller's original cube-tiling conjecture remains open in dimension 7." The links you give are on the graph-theoretic version and do not resolve the question about 7d cube tilings. The issue is the following: if the graph theoretic version is false in a certain dimension d, then the tiling version is also false in d. And if the cube tiling version is false in a certain dimension d, then the graph version is false in some higher dimension d' > d. So our knowledge about the graph version doesn't allow us to determine the exact dimension at which the tiling version fails. There's a note about this in the article, in the third paragraph of the "Keller graphs" section, but perhaps it's too cryptic. —David Eppstein (talk) 00:23, 18 April 2013 (UTC)[reply]

I see. Thank you for clarification and sorry for confusion. Maxal (talk) 00:55, 18 April 2013 (UTC)[reply]

Did you know nomination[edit]

The following is an archived discussion of the DYK nomination of the article below. Please do not modify this page. Subsequent comments should be made on the appropriate discussion page (such as this nomination's talk page, the article's talk page or Wikipedia talk:Did you know), unless there is consensus to re-open the discussion at this page. No further edits should be made to this page.

The result was: promoted by SL93 (talk) 07:50, 20 April 2021 (UTC)[reply]

(

Comment or view
Article history

)

... that a mathematical conjecture about tiling space by cubes was transformed into a problem in graph theory that became a benchmark for clique-finding algorithms? Source: Debroni et al.: "Keller graphs are in the benchmark set of clique problems from the DIMACS clique challenge"

Reviewed: Marion Miley

Improved to Good Article status by David Eppstein (talk). Self-nominated at 20:14, 1 April 2021 (UTC).[reply]

(checked Debroni source for hook); article is long enough and new enough; hook is about as suitable for a popular audience as is possible here. Chiswick Chap (talk) 14:20, 7 April 2021 (UTC)[reply]

Solution[edit]

@Dedhert.Jr Currently it mentions the 1992 breakthrough in the lede, but not the 2019 solution that finished proving it for all the dimensions, just 'it is now known'. That should be done better, but you reverted my edit to do this. PhotographyEdits (talk) 07:37, 3 June 2024 (UTC)[reply]

The lead should explain the summary of the whole article. I think it's already explained in the second paragraph, stating that Lagarias and Shor in 1992 explained that conjecture on Keller's graph dimension is false in more than ten dimensions, after which the refinement version says it is false in more than seven dimensions. Your writing about the 2019 solution that finished proving it for all the dimensions (maybe did you mean at least seven dimensions?) already explained in such. Dedhert.Jr (talk) 10:55, 3 June 2024 (UTC)[reply]