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 <https://www.youtube.com/watch?v=8SZPNzO5hQU>`_)
| `David P. Williamson <http://www.davidpwilliamson.net/work>`_ (`Operations Research and Information Engineering <http://www.orie.cornell.edu/>`_, 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.