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

# How to cut a set into two pieces

by

William Zwicker
Union College

November 4, 2013
5 pm
Bailey Hall 207

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

## Abstract:

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