Monday, June 26, 2017
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
We discuss results ond open problems on empty convex polygons in planar point
sets related to the Empty Hexagon Theorem described below.
Let P be a finite set of points in general position in the plane (i.e., no
three points lie on a line). A convex k-gon G is called a k-hole (or
empty convex k-gon) of P, if all vertices of G lie in P and no point
of P lies inside G. Erdős (early 70's) asked if, for a fixed k, any
sufficiently large point set in general position contains a k-hole. Harborth
(1978) proved that any set of 10 points in general position in the plane
contains a 5-hole and gave a construction of 9 points with no 5-hole.
Horton (1983) constructed, for any n, a set of n points in general
position in the plane with no 7-hole. The remaining case k=6 became a
well-known open problem. Ten years ago Gerken and Nicolás independently
solved this problem by showing that any sufficiently large planar point set in
general position in the plane contains a 6-hole.
Colloquium - 16:00
Abstract:
In this talk we focus on matching markets under preferences. In particular, we investigate a scenario where each agent in a market has an ordered preference list over some other agents and our task is to find an optimal matching of the agents so that it represents a certain global social welfare. A matching M is popular if there is no matching M' such that the vertices that prefer M' to M outnumber those that prefer M to M'. In this talk, we will summarize known results about the existence and structure of popular matchings under various assumptions such as bipartite and general graphs, strictly ordered lists and lists containing ties. We will also pose several open questions of this quickly growing field.