On the Zarankiewicz Problem for Intersection Hypergraphs

International audienceLet $d$ and $t$ be fixed positive integers, and let $K^d_{t,\ldots,t}$ denote the complete $d$-partite hypergraph with $t$ vertices in each of its parts, whose hyperedges are the $d$-tuples of the vertex set with precisely one element from each part.According to a fundamental theorem of extremal hypergraph theory, due to Erd\H os~\cite{E64}, the number of hyperedges of a $d$-uniform hypergraph on $n$ vertices that does not contain $K^d_{t,\ldots,t}$ as a subhypergraph, is $n^{d-\frac{1}{t^{d-1}}}$. This bound is not far from being optimal.We address the same problem restricted to {\em intersection hypergraphs} of $(d-1)$-dimensional {\em simplices} in $\Re^d$. Given an $n$-element set $\S$ of such simplices, let $\HH^d(\S)$ denote the $d$-uniform hypergraph whose vertices are the elements of $\S$, and a $d$-tuple is a hyperedge if and only if the corresponding simplices have a point in common. We prove that if $\HH^d(\S)$ does not contain $K^d_{t,\ldots,t}$ as a subhypergraph, then its number of edges is $O(n)$ if $d=2$, and $O(n^{d-1+\epsilon})$ for any $\epsilon>0$ if $d \geq 3$. This is almost a factor of $n$ better than Erd\H os's above bound. Our result is tight, apart from the error term $\epsilon$ in the exponent.In particular, for $d=2$, we obtain a theorem of Fox and Pach~\cite{FP08}, which states that every $K_{t,t}$-free intersection graph of $n$ {\em segments} in the plane has $O(n)$ edges. The original proof was based on a separator theorem that does not generalize to higher dimensions. The new proof works in any dimension and is simpler: it uses {\em size-sensitive cuttings}, a variant of random sampling. We demonstrate the flexibility of this technique by extending the proof of the planar version of the theorem to intersection graphs of $x$-monotone curves