Prefix-reversal Gray codes

PhD Student Seminar
Open to the Public
Zrinyi u. 14
Wednesday, February 25, 2015 - 2:00pm
Add to Calendar
Wednesday, February 25, 2015 - 2:00pm

Abstract: While designing combinatorial algorithms one faces the
problem of presenting the combinatorial objects in the machine. For
example, the exhaustive search or random sampling algorithms on the
certain space of objects require keeping the whole list of the objects
in memory. There comes a need in efficient algorithms of generating
and listing the combinatorial objects, which can be achieved by using
Gray codes.
The term 'Gray code' was introduced in 1953 with the classic
construction of binary reflected code, which is a scheme for listing
all n-bit binary numbers, so that successive numbers differ in exactly
one bit. The notion of combinatorial Gray codes was set later in 1980
and refers to any method for generating combinatorial objects, so that
successive objects differ in some pre-specified small way. In this
talka quick survey is provided on the existing combinatorial Gray
We also consider the notion of Prefix-reversal Gray codes, which
correspond to the Hamilton cycles or paths in the Pancake graph, which
is the Cayley graph on the symmetric group with the generating set of
prefix-reversals. The two scenarios are known to obtain
prefix-reversal Gray codes. The first was given by S. Zaks in 1984,
the second was suggested by A. Williams and J. Sawada in 2013 and the
constructions were given in purely algorithmic way. We present the
relation between Prefix-reversal Gray codes and the maximal sets of
independent cycles in the Pancake graph, provide the series of these
cycles and study the existence of Prefix-reversal Gray codes on them,
spiced with some open questions at the end of the talk.
This work is joint work with E. Konstantinova, Sobolev Institute of
Mathematics, Novosibirsk, Russia.