An update on the middle levels problem

Details An update on the middle levels problem An update on the middle levels problem

2006-08-19

arxiv.org/abs/math/0608485v1

Mathematics

Combinatorics

11 pages, 5 figures

Scientific paper

The middle levels problem is to find a Hamilton cycle in the middle levels, M_{2k+1}, of the Hasse diagram of B_{2k+1} (the partially ordered set of subsets of a 2k+1-element set ordered by inclusion). Previously, the best result was that M_{2k+1} is Hamiltonian for all positive k through k=15. In this note we announce that M_{33} and M_{35} have Hamilton cycles. The result was achieved by an algorithmic improvement that made it possible to find a Hamilton path in a reduced graph of complementary necklace pairs having 129,644,790 vertices, using a 64-bit personal computer.

Affiliated with

Also associated with

No associations

Rating

An update on the middle levels problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An update on the middle levels problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An update on the middle levels problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-95415