COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Summer 2005

Recent discoveries have shown a wide range of different roles that RNA molecules play in the workings of cells, and how important deciphering structure is to the classification of RNA molecules. Comparing RNA structures computationally is very difficult; while simple unknotted structures can be compared in polynomial time, generalizations of knotted structures have previously been shown to be NP-complete. These generalizations, however, do not resemble actual structures. A specific set of restrictions common to most RNA structures will be discussed and a polynomial time algorithm for comparing restricted structures will be presented. While the polynomials for the running time and space of this algorithm still appear to be of prohibitively high degree, a technique for reducing the resource usage can be used, and its results will be discussed.

For linear functions x(n) and y(n), a recurrence relation is "meta-Fibonacci" if it has the doubly recursive form a(n) = a( x(n) - a(n-1) ) + a( y(n) - a(n-2) ). This recurrence relation has been studied by various researchers for particular functions x and y; for example, by John Conway, Douglas Hofstadter, and Steven Wolfram, but in general it's solutions are mysterious and often chaotic. We study a well behaved case, namely when x(n) = y(n)+1 = n-s for some natural number s. For this case we show that the a(n) numbers arise naturally in studying the number of leaves at the largest level in certain infinite sequences of binary trees, restricted compositions of an integer, and binary compact codes. For this family of meta-Fibonacci sequences and two families of related sequences we derive ordinary generating functions and recurrence relations. Included in these families of sequences are several well-known sequences in the Online Encyclopedia of Integer Sequences (OEIS).

Fullerenes are carbon molecules that have in most recent times sparked the interest of many people from a variety of subject areas including mathematics and computer science. Mathematically, fullerene structures correspond to planar graphs that are 3-regular with faces of either 5 or 6 sides. The study of these mathematical models has led to many interesting inquiries and results; there are even those for which the relevance to the chemistry of the actual fullerenes is immediately apparent. In many ways the fact that we have a means to model fullerenes, due to their ideal structure, is itself an aide in research. Thus it makes sense to enhance this visual or graphical component of fullerene research. Computer programs are often used as a tool for graphics generation and display and often play a role in the discovery of conjectures. Among other things, in this talk we will make use of FUIGUI, a system for visualizing fullerenes and aiding research regarding their parameters. This talk requires some basic knowledge of graph theory.

This is joint work with Wendy Myrvold.