[Mathclub-members] Colloquium on Monday
kaul at math.iit.edu
Fri Nov 16 18:40:28 CST 2007
I am sorry for any multiple notifications.
We have two talks next week on Monday and Tuesday at 4:40pm by Ryan
Martin who will be visiting us from Iowa State University.
I want to strongly encourage you all, especially students, to attend the
colloquium on Monday as the speaker has promised to make the talk
accessible to a general audience. And, he is a good speaker.
I hope to see you all there.
Monday Colloquium: 4:40pm, E1 106
The edit distance in Graphs
The edit distance problem relates to questions in theoretical computer
science but there are also some origins in evolutionary biology. In
computing edit distance, we want to know how many deletions or additions
of edges in a graph are required in order to eliminate a specified
induced subgraph. We will describe the problem in full, giving some of
the basic results and techniques for finding bounds on edit distance. In
the process, we will define the so-called binary chromatic number, and
show how it bounds the edit distance. Furthermore, we will see how the
problem relates to Szemeredi's regularity lemma, Turan's theorem and
Tuesday Seminar: 4:40pm, E1 244
Computing edit distance
We will continue the edit distance problem, giving further results and
more insight into the proofs. The concept of colored regularity graphs
of Alon and Stav are used to compute edit distance without direct use of
Szemeredi's regularity lemma. In addition, there is a weighted version
of Turan's theorem which may be of independent interest.
More information about the Mathclub-members