[ugrads] [Mathclub-members] Colloquium on Monday

[Hemanshu Kaul]

Hello all,

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.

Hemanshu

--------------------

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
Ramsey theory.
--------------------

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.
--------------------

_______________________________________________
Mathclub-members mailing list
Mathclub-members at math.iit.edu
http://math.iit.edu/mailman/listinfo/mathclub-members