Discrete Mathematics and Optimization Seminar
JANOS PACH |
City College and Courant Institute, New York
Monday April 2nd at 4.30pm
Burnside 1205
Title. Turan-type results on intersection graphs.
Abstract.
We establish several geometric extensions of the Lipton-Tarjan
separator theorem for planar graphs. For instance,
we show that any collection C of Jordan curves in the plane with a total
of m crossings has a partition into three parts
C=S ∪ C1 ∪ C2 such that
|S|=O(√m), max (|C1|,|C2|) ≤ 2|C|/3,
and no element of C1
has a point in common with any element
of C2. These results are used to obtain various properties
of intersection patterns
of geometric objects in the plane. In particular, we prove that if a graph G
can be obtained as the intersection graph of
n convex sets in the plane and it
contains no complete bipartite graph Kk,k as a subgraph,
then the number of edges of G
cannot exceed ck n for a suitable constant ck.
Joint work with Jacob Fox.