On the Zarankiewicz problem for intersection hypergraphs

Mustafa, Nabil H. and Pach, János (2016) On the Zarankiewicz problem for intersection hypergraphs. JOURNAL OF COMBINATORIAL THEORY SERIES A, 141. pp. 1-7. ISSN 0097-3165

Preview

Text intersectionhypergraphsGD082915.pdf Download (252kB) | Preview

Abstract

Let d and t be fixed positive integers, and let Kd t,...,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 Erdos [6], the number of hyperedges of a d-uniform hypergraph on n vertices that does not contain Kd t,...,t as a subhypergraph, is nd-1td-1. This bound is not far from being optimal. We address the same problem restricted to intersection hypergraphs of (d-1)-dimensional simplices in Rd. Given an n-element set S of such simplices, let Hd(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 Hd(S) does not contain Ktd....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 Erdos'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 [7], which states that every Kt,t-free intersection graph of n 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 size-sensitive cuttings, a variant of random sampling. © 2016 Elsevier Inc.

Actions (login required)

Edit Item