Turán-type results for intersection graphs of boxes

Abstract

In this short note, we prove the following analog of the Kővári-Sós-Turán theorem for intersection graphs of boxes. If $G$ is the intersection graph of $n$ axis-parallel boxes in ${\mathbb{R}}^d$ such that $G$ contains no copy of $K_{t,t}$, then $G$ has at most $ctn(\log n{)}^{2d+3}$ edges, where $c=c(d)>0$ only depends on $d$. Our proof is based on exploring connections between boxicity, separation dimension and poset dimension. Using this approach, we also show that a construction of Basit et al. of $K_{2,2}$-free incidence graphs of points and rectangles in the plane can be used to disprove a conjecture of Alon et al. We show that there exist graphs of separation dimension 4 having superlinear number of edges.

4 pages