• Calendar

January 13, Tuesday
13:00 – 15:00

The intersection graph of a family $F$ of $n$ sets is a graph on $n$ vertices which correspond to the sets. We connect two vertices by an edge iff the corresponding sets intersect. We show that if $F$ is a family of $n$ semi-algebraic sets, then the intersection graph of $F$ contains either a complete bipartite subgraph or an empty bipartite subgraph on $cn$ vertices, where $c$ is an absolute constant which depends only on the complexity of the semi-algebraic sets. For example, given a collection of $n$ balls in $R^3$, one can always find two disjoint sets of balls $S_1$ and $S_2$ ($|S_1|,|S_2|>cn$) $such that either every ball from $S_1$ intersects every ball from $S_2$ or no ball from $S_1$ intersects any ball from $S_2$. We also show that the intersection graph of semi-algebraic sets has either a clique or an independent set of size $n^\epsilon$ where $\epsilon$ depends only on the complexity of the semi-algebraic sets. This shows the Erdos-Hajnal property for that rather big class of graphs.

Joint work with Noga Alon, Janos Pach, and Rados Radoicic.