Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
On the Zarankiewicz Problem for Intersection Hypergraphs
verfasst von : Nabil H. Mustafa, János Pach
Erschienen in: Graph Drawing and Network Visualization
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let 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ős [7], 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 intersection hypergraphs of \((d-1)\)-dimensional simplices in \(\mathbb {R}^d\). Given an n-element set \(\mathcal {S}\) of such simplices, let \(\mathcal {H}^d(\mathcal {S})\) denote the d-uniform hypergraph whose vertices are the elements of \(\mathcal {S}\), and a d-tuple is a hyperedge if and only if the corresponding simplices have a point in common. We prove that if \(\mathcal {H}^d(\mathcal {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 \ge 3\). This is almost a factor of n better than Erdős’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 [8], which states that every \(K_{t,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. 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.