Spring 2018
===========
We meet 4:00--5:30 in Evans room 1011.
Monday, February 26
-------------------
| **Vector Representations of Graphs and the Maximum Cut Problem** (:download:`slides <../pdfs/2018-02-26-williamson.pdf>` | `video `_)
| `David P. Williamson `_ (`Operations Research and Information Engineering `_, Cornell University)
In this talk, I will look at a classical problem from graph theory of finding a
large cut in a graph. We'll start with a 1967 result of ErdÅ‘s that showed that
picking a random partition of the graph finds a cut that is at least half the
largest possible cut. We'll then describe a result due to Goemans and myself
from 1995 that shows that by representing the graph as a set of vectors, one
per vertex, and optimizing the set, one can find a cut of size at least .878
the largest possible. If time permits, we'll see an additional application of
this vector representation to either clustering or coloring.