The Library
A short proof of the middle levels theorem
Tools
Gregor, Petr, Mutze, Torsten and Nummenpalo, Jerri (2018) A short proof of the middle levels theorem. Discrete Analysis (Paper No. 8). pp. 1-12. doi:10.19086/da.3659 ISSN 2397-3129.
|
PDF
WRAP-short-proof-middle-levels-theorem-Mutze-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (871Kb) | Preview |
Official URL: https://doi.org/10.19086/da.3659
Abstract
Consider the graph that has as vertices all bitstrings of length~$2n+1$ with exactly~$n$ or~$n+1$ entries equal to~1, and an edge between any two bitstrings that differ in exactly one bit.
The well-known middle levels conjecture asserts that this graph has a Hamilton cycle for any~$n\geq 1$.
In this paper we present a new proof of this conjecture, which is much shorter and more accessible than the original proof.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Graph theory, Hamiltonian graph theory, Mathematics, Computer science -- Mathematics | ||||||
Journal or Publication Title: | Discrete Analysis | ||||||
Publisher: | Diamond Open Access Journals | ||||||
ISSN: | 2397-3129 | ||||||
Official Date: | 21 May 2018 | ||||||
Dates: |
|
||||||
Number: | Paper No. 8 | ||||||
Page Range: | pp. 1-12 | ||||||
DOI: | 10.19086/da.3659 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 19 June 2019 | ||||||
Date of first compliant Open Access: | 25 June 2019 | ||||||
Related URLs: | |||||||
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