Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655063 | Journal of Combinatorial Theory, Series A | 2016 | 7 Pages |
Let d and t be fixed positive integers, and let Kt,…,td 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ős [6], the number of hyperedges of a d-uniform hypergraph on n vertices that does not contain Kt,…,td 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)(d−1)-dimensional simplices in RdRd. Given an n -element set SS of such simplices, let Hd(S)Hd(S) denote the d -uniform hypergraph whose vertices are the elements of SS, 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)Hd(S) does not contain Kt,…,td as a subhypergraph, then its number of edges is O(n)O(n) if d=2d=2, and O(nd−1+ϵ)O(nd−1+ϵ) for any ϵ>0ϵ>0 if d≥3d≥3. This is almost a factor of n better than Erdős's above bound. Our result is tight, apart from the error term ϵ in the exponent. In particular, for d=2d=2, we obtain a theorem of Fox and Pach [7], which states that every Kt,tKt,t-free intersection graph of n segments in the plane has O(n)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.