| DATE: | Wednesday, November 19th |
| TIME: | 4:45 PM - 5:45 PM |
| PLACE: | McConnell 320 |
| TITLE: | Computational Geometry for World Peace: some open problems |
| SPEAKER: | David Bryant, School of Computer Science, McGill University. |
A split is a bipartition of a finite set into two non-empty parts. Any collection of splits may be represented using a splits graph: a bipartite, edge coloured graph, partially labelled by X. The colour classes correspond to the splits. Removing the edges associated with a split A|B partitions the graph into two convex connected parts, one containing all the vertices labelled by A, the other containing all the vertices labelled by B. These graphs are drawn with straight edges so that edges of the same colour are parallel with the same length.
Splits graphs provide an elegant visual representation of groupings
within a data set. They have been applied to a wide variety of
different domains: from plant evolution to African drumming to UN
votings patterns (hence the title) to viral and bacterial
identification to comparative linguistics to English literature. I'll
talk about some of these applications on Wednesday. However my main
emphasis will be on the mathematics of splits graphs and the
computational problem of constructing and drawing them. This is work in
progress... there are many open problems.