On the Zarankiewicz Problem for Intersection Hypergraphs

Mustafa, Nabil H. and Pach, János (2015) On the Zarankiewicz Problem for Intersection Hypergraphs. In: Graph Drawing and Network Visualization. Lecture Notes in Computer Science (9411). Springer, Berlin, pp. 207-216. ISBN 978-3-319-27260-3

Preview

Text intersectionhypergraphsGD082915.pdf Download (244kB) | Preview

Abstract

Let d and t be fixed positive integers, and let Kdt,…,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 Kdt,…,t as a subhypergraph, is nd−1td−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 Rd. Given an n-element set § of such simplices, let \HHd(§) denote the d-uniform hypergraph whose vertices are the elements of §, and a d-tuple is a hyperedge if and only if the corresponding simplices have a point in common. We prove that if \HHd(§) does not contain Kdt,…,t as a subhypergraph, then its number of edges is O(n) if d=2, and O(nd−1+ϵ) for any ϵ>0 if d≥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 ϵ in the exponent. In particular, for d=2, we obtain a theorem of Fox and Pach~\cite{FP08}, which states that every Kt,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.

Actions (login required)

Edit Item