^June July – 2010 ^August

In recent studies non-coding RNA gets more attention. For these RNAs that perform various roles within the cell, structure is much more important then the sequence. This talk will encompass: Different approaches to gauge similarity/distance between RNA structures. Contraction of RNA structures from favoritble building blocks in order to manifacture active RNAs. Extended RNA inverse - design RNA that will fold to a desired structure and physical properties.

Let H be a graph. By TH we denote the graphs obtained from H by replacing the edges of H with vertex-disjoint paths that internally consist of an arbitrary number of degree two vertices (possibly zero). A member of TH is called a topological H (or a subdivision of H).

The question: "what is the structure of a graph containing no member of TH as a subgraph, for some fixed H?" is one of the main problems in graph theory today since the 1930s. Such "TH-free" graph families are found in many of the so called "pearls" of graph theory: Kuratowski's theorem, Tutte's integer-flow conjectures, Hajos' conjecture, Kelmans-Seymour conjecture and more.

Over the years, some partial results unfolding the structure of such "TH-free" graph families were discovered for a small number of configurations H. Sadly, each such result required some special handeling well-suited for the specific H being considered. Thus, no systematic approach towards answering the above question is known (or even conjectured).

In the last year or so I have been trying to make progress on the above question.

In the talk I propose I shall begin with an overview of the notion of "subdivisions in graphs". I then hope to introduce some of my results regarding "TH-free" graphs and spend some time on the notion of "semi-topological minors" (special forms of subdivisions). I will make an attempt to include some of my more recent results regarding the Kelmans-Seymour conjecture postulating that: "the 5-connected nonplanar graphs contain a TK_5".