The q-analog of the middle levels problem

Abstract: The well-known middle levels problem is to find a Hammiltonian cycle in the graph induced from the binary Hamming graph

c H_{2} (2 k + 1)

by the words of weight

k

or

k + 1

. In this paper we define the

q

-analog of the middle levels problem. Let

n = 2 k + 1

and let

q

be a power of a prime number. Consider the set of

(k + 1)

-dimensional subspaces and the set of

k

-dimensional subspaces of

F_{q}^{n}

. Can these subspaces be ordered in a way that for any two adjacent subspaces

X

and

Y

, either

X s u b s e t Y

or

Y s u b s e t X

? A construction method which yields many Hamiltonian cycles for any given

q

and

k = 2

is presented.

Recommendations

Cites Work

This page was built for publication: The \(q\)-analog of the middle levels problem