Up: Student Seminars for 2013
Top: Math Department Student Seminars

How to cut a set into two pieces


William Zwicker
Union College

November 4, 2013
5 pm
Bailey Hall 207

Refreshments will be served in Bailey Hall 204 at 4:45


Suppose $S$ is a finite set, and we have some measure $w(x,y)$ of the amount by which an individual element $x$ of $S$ is "above" another element $y$. Our goal will be to divide $S$ into pieces $S_{T}$ and $S_{B}$ in the way that maximizes the total separation of these pieces, measured by summing all individual amounts$ w(x,y)$ by which an element $x$ of $S_{T}$ is above an element $y$ of $S_{B}$ (See picture):

We consider several settings:

• $S$ is a set of real numbers, and $w(x,y) = x - y . . .$ or $w(x,y) = |x - y|$

• $S$ is a set of points in Euclidean $k$-space $R^{k}$ and $w(x,y) = x - y ...$ or $w(x,y) = ||x - y||$

• $S$ is a set of vertices in a graph$^1$ and $w(x,y)$ is an arbitrary weight assigned to the directed edge from $x$ to $y ...$ or to the undirected edge between $x$ and $y$

Maximizing total separation is easy for some of these settings, but difficult for others. A connection to the mathematical theory of voting arises, which is surprising only if you haven't already realized that the mathematical theory of voting is connected to everything.

* Joint research with Nicolas Houy (CNRS and University of Lyon), Jérôme Lang (CNRS and University of Paris Dauphine), Conal Duddy and Ashley Piggins (National University of Ireland Galway).

$^1$ A graph in the sense of Math 219 (rather than the graph of a function, as in Calculus).

For additional information, send e-mail to math@union.edu or call (518) 388-6246.
Up: Student Seminars for 2013
Top: Math Department Student Seminars

Union College Math Department Home Page
Comments to: math@union.edu
Created automatically on: Tue Oct 23 07:28:05 EDT 2018