Talk: Trees Invariant Under a Half-Turn


The work to be presented here grew out of some theoretical models proposed by David Halitsky in an attempt to describe structural redundancies in DNA and proteins. Halitsky is a linguist by training but has spent most of his career in computing. Underlying his ideas are two main principles. First, natural language, DNA, amino acid sequences in proteins, and even computer databases are all methods for storing and communicating information, and he posits that there should be certain basic structural similarities among them. Second, he believes that seemingly complex low dimensional phenomena are sometimes the result of a projection of very regular higher dimensional structures. Symmetry is, of course, a way of measuring structure and redundancy, and it is Halitsky's recognition of previously unnoted symmetries in language-theoretic structures which differentiates his bio-molecular application of these constructs from their well-known application to bio-informatics by David Searls. ?This talk will focus on some mathematics that was inspired by Halitsky's ideas and questions. In particular, it will be concerned with trees represented in a discrete torus, namely, $Z_n \times Z_n$. Here $Z_n$ carries the structure of a ring as well as the natural {\bf cyclic} order. In this context, it makes sense to call a mapping of the form ${\bf x} \longrightarrow {\bf c} - {\bf x}$ a {\it half-turn} in analogy with the Euclidean situation. Cutting the torus along two fundamental cycles allows it to be flattened out. The same structure on the torus can give rise to many different trees. One of Halitsky's main problems was to characterize those trees which can arise from a set of points on the torus which is left invariant by some half-turn. A solution will be presented in this talk. Halitsky was originally motivated to ask this question when he noted empirically that three families of trees that are important in linguistics have a matching property which turns out to be equivalent to invariance under a half-turn.