### DIMACS Theoretical Computer Science Seminar

Title: A Center Transversal Theorem for Hyperplanes Arrangements

Speaker: **Stefan Langerman**, Université Libre de Bruxelles

Date: Wednesday, January 30, 2013 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

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 R^2,
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.
Back to Graph Drawing (and in the plane), we completely solve the open
problem that motivated our search: there is no set of n labelled lines
that are universal for all n-vertex labelled planar graphs.
This is joint work with Vida Dujmovic.

See: http://paul.rutgers.edu/~yixinxu/theory-spring13.html