Kazuyuki Amano

  1. A Note on the Middle Levels Conjecture.

    Authors: Manabu Shimada, Kazuyuki Amano
    Subjects: Discrete Mathematics
    Abstract

    The middle levels conjecture asserts that there is a Hamiltonian cycle in the
    middle two levels of $2k+1$-dimensional hypercube. The conjecture is known to
    be true for $k \leq 17$ [I.Shields, B.J.Shields and C.D.Savage, Disc. Math.,
    309, 5271--5277 (2009)]. In this note, we verify that the conjecture is also
    true for $k=18$ by constructing a Hamiltonian cycle in the middle two levels of
    37-dimensional hypercube with the aid of the computer. We achieve this by
    introducing a new decomposition technique and an efficient algorithm for
    ordering the Narayana objects.

Syndicate content