Informatics Seminar (Perspective in Informatics 4B) 2010 - 2011
December 3 (Fri), 16:30 - 18:00
- Place:
Lecture Hall 1, Faculty of Engineering Bldg. No.10, Main Campus
- Title:
A Center Transversal Theorem for Hyperplanes Arrangements
- Speaker:
Stefan Langerman (Université Libre de Bruxelles)
- Abstract:
Motivated by an open problem from graph drawing, we study
several partitioning problems for line and hyperplane arrangements. We
prove a ham-sandwich cut theorem: given two sets of n lines in R2,
there
is a line L such that in both line sets, for both halfplanes delimited
by L, there are sqrt{n} lines which pairwise intersect in that
halfplane, and this bound is tight; a centerpoint theorem: for any set
of n lines there is a point such that for any halfplane containing
that point there are Omega(sqrt{n}) of the lines which pairwise
intersect in that halfplane.
We generalize those results in higher dimension and obtain a center
transversal theorem, a same-type lemma, and a positive fraction
Erdos-Szekeres theorem for hyperplane arrangements.
This is done by formulating a generalization of the center transversal
theorem which applies to set functions that are much more general than
measures.
This is joint work with Vida Dujmovic.
Kyoto University
> Graduate School of Informatics
> International Courses
> Informatics Seminar