The Library
Proof of the middle levels conjecture
Tools
Mutze, Torsten (2016) Proof of the middle levels conjecture. Proceedings of the London Mathematical Society, 112 (4). pp. 677-713. doi:10.1112/plms/pdw004 ISSN 0024-6115.
|
PDF
WRAP-proof-middle-levels-conjecture-Mutze-2016.pdf - Accepted Version - Requires a PDF viewer. Download (1407Kb) | Preview |
Official URL: https://doi.org/10.1112/plms/pdw004
Abstract
Define the middle layer graph as the graph whose vertex set consists of all bitstrings of length $2n+1$ that have exactly $n$ or $n+1$ entries equal to 1, with an edge between any two vertices for which the corresponding bitstrings differ in exactly one bit. The middle levels conjecture asserts that this graph has a Hamilton cycle for every $n\geq 1$. This conjecture originated probably with Havel, Buck and Wiedemann, but has also been attributed to Dejter, Erd{\H{o}}s, Trotter and various others, and despite considerable efforts it resisted all attacks during the last 30 years.
In this paper we prove the middle levels conjecture. In fact, we construct $2^{2^{\Omega(n)}}$ different Hamilton cycles in the middle layer graph, which is best possible.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Hamiltonian graph theory, Computer science -- Mathematics, Graph theory | ||||||
Journal or Publication Title: | Proceedings of the London Mathematical Society | ||||||
Publisher: | Oxford University Press | ||||||
ISSN: | 0024-6115 | ||||||
Official Date: | 1 March 2016 | ||||||
Dates: |
|
||||||
Volume: | 112 | ||||||
Number: | 4 | ||||||
Page Range: | pp. 677-713 | ||||||
DOI: | 10.1112/plms/pdw004 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | “This is the accepted version of the following article: Torsten Mütze, Proof of the middle levels conjecture, Proceedings of the London Mathematical Society, Volume 112, Issue 4, April 2016, Pages 677–713 , which has been published in final form at https://doi.org/10.1112/plms/pdw004 | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 17 June 2019 | ||||||
Date of first compliant Open Access: | 25 June 2019 | ||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year