Minimal enumerations of subsets of a finite set and the middle level problem

https://doi.org/10.1016/S0166-218X(00)00363-2Get rights and content
Under an Elsevier user license
open archive

Abstract

A well-known problem of the existence of a Hamilton cycle in the middle two levels of the n-dimensional Boolean lattice, n is odd, is considered. The necessary and sufficient conditions for an n-symbol sequence to be a code of the cycle are obtained. It is shown that symbols of the sequence must satisfy certain properties of an uniform distribution in the sequence.

Keywords

Middle level problem
Hamilton cycle

Cited by (0)

Translated from Discrete Anal. Oper. Res. Novosibirsk 4(4) (1997) 6–12.

1

Supported by the Russian Foundation for Fundamental Research (Grant 96–01–01800) and the Federal Target Program “Integration” (Project 473).