Markov partitions and 1-dimensional tilings
Maciej Wojtkowski

Bi-partitions are partitions of the 2-dim torus by two parallelograms.
They give rise to 2-periodic tilings of the plane, and further to
1-dim tilings which have a host of well known combinatorial properties,
e.g. these are Sturmian sequences. When a bi-partition is a Markov partition
for a hyperbolic toral automorphism (= Berg partition),
the tilings are substitution tilings. The substitutions preserving Sturmian
sequences are known to have the ``3-palindrome property''. The number
of different substitutions was determined by Seebold '98, and the number
of nonequivalent Berg partitions by Siemaszko and Wojtkowski '11.
The two formulas coincide. Using tilings we give a simpler proof for
the last result. It shows that every combinatorial substitution preserving
a Sturmian sequence is realized geometrically as a Berg partition.