Algebraic Combinatorics Seminar
####
**
UNIVERSITY OF KENTUCKY **

ALGEBRAIC COMBINATORICS SEMINAR

845 PATTERSON OFFICE TOWER

SPRING 2004

####

##
On some famous sequences

Sergey Kitaev

###
Monday, February 9, 2004

1:00 pm, 845 Patterson Office Tower

####
Abstract:

The Arshon sequence was given in 1937 in connection with the problem
of constructing a square-free sequence on a given alphabet, that is, a
sequence that does not contain any subword of the type XX, where X is
any non-empty word over the alphabet. The question of the existence
of such a sequence, as well as the question of the existence of
sequences avoiding other kinds of repetitions, were studied in
algebra, discrete analysis, and in dynamical systems.

The Dragon curve (the paperfolding sequence) was discovered by
physicist John Heighway and was described by Martin Gardner in
1978. It is defined as follows: we fold a sheet of paper in half, then
fold in half again, and again, etc. and then unfold in such way that
each crease created by the folding process is opened out into a
90-degree angle. The "curve" refers to the shape of the partially
unfolded paper as seen edge on. It turns out that the Dragon curve is
related to the sigma-sequence that was used by Evdokimov in 1968 in
order to construct chains of maximal length in the n-dimensional unit
cube.

The Peano curve was studied by the Italian mathematician Giuseppe
Peano in 1890 as an example of a continuous space filling curve. The
Peano infinite word is a discrete analog of the Peano curve.

Are there any similarities between the Arshon sequence, the Dragon
curve, and the Peano infinite word in terms of combinatorics on words?
In this talk, I will answer this question using some recent results.