**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 ∪ C*_{1} ∪ C_{2} such that
* |S|=O(√m)*, * max (|C*_{1}|,|C_{2}|) ≤ 2|C|/3,
and no element of *C*_{1}

has a point in common with any element
of *C*_{2}. 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 *K*_{k,k} as a subgraph,
then the number of edges of *G*

cannot exceed *c*_{k} n for a suitable constant *c*_{k}.
Joint work with Jacob Fox.