Discrete Mathematics and Optimization Seminar

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.