Density and regularity theorems for semi-algebraic hypergraphs

Fox, Jacob and Pach, János and Suk, Andrew (2015) Density and regularity theorems for semi-algebraic hypergraphs. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2015.01.04-2015.01.06, San Diego.

Preview

Text regularity031014.pdf Download (437kB) | Preview

Abstract

A k-uniform semi-algebraic hypergraph H is a pair (P, E), where P is a subset of ℝd and E is a collection of fc-tuples {<inf>p1</inf> ⋯ <inf>Pk</inf>} ∪ P such that (<inf>p1</inf> ⋯ <inf>Pk</inf>) ∈ E if and only if the kd coordinates of the pi-s satisfy a boolean combination of a finite number of polynomial inequalities. The complexity of H can be measured by the number and the degrees of these inequalities and the number of variables (coordinates) kd. Several classical results in extremal hypergraph theory can be substantially improved when restricted to semi-algebraic hypergraphs. Substantially improving a theorem of Fox, Gromov, Lafforgue, Naor, and Pach, we establish the following "polynomial regularity lemma": For any 0 < ε < 1/2, the vertex set of every k-uniform semi-algebraic hypergraph H = (P, E) can be partitioned into at most (l/ε)c parts P<inf>1</inf>, P2⋯ as equal as possible, such that all but at most an e-fraction of the k-tuples of parts (P<inf>i1</inf>,P<inf>ik</inf>) are homogeneous in the sense that either every k-tuple (p<inf>i1</inf>,P<inf>ik</inf>.) ∈ P<inf>i1</inf> x · · · x P<inf>ik</inf> belongs to E or none of them do. Here c > 0 is a constant that depends on the complexity of H. We also establish an improved lower bound, single exponentially decreasing in k, on the best constant δ> 0 such that the vertex classes P<inf>1</inf>,⋯P<inf>k</inf> of every k-partite k-uniform semi-algebraic hypergraph H = (P<inf>1</inf> ∪ ⋯ ∪ P<inf>k</inf>, E) with |E| ≥ εIIk<inf>j=1</inf>|P<inf>i</inf>| have, for 1 ≤ i ≤ k, δ|P<inf>i</inf>|-element subsets P′<inf>i</inf>⊆ P<inf>i</inf> satisfying P′<inf>1</inf> x⋯ x P′<inf>k</inf> ⊆ E. The best previously known lower bound on δ due to Bukh and Hubard decreased double exponentially fast in k. We give three geometric applications of our results. In particular, we establish the following strengthening of the so-called same-type lemma of Barany and Valtr: Any disjoint finite sets P<inf>1</inf>,⋯,P<inf>k</inf> ∪ ℝd (k < d) have for 1 ≥ i ≥ k subsets P′<inf>i</inf> of size at least 2-o (d3k log k)|P<inf>i</inf>| with the property that every k-tuple formed by taking one point from each P′<inf>i</inf> has the same order type. The above techniques carry over to property testing. We show that for any typical hereditary hypergraph property Q, there is a randomized algorithm with query complexity (1/ε)c (o) to determine (with probability at least .99) whether a k-uniform semi-algebraic hypergraph H = (P, E) with constant description complexity is e-near to having property Q, that is, whether one can change at most ε|P|k hyperedges of H in order to obtain a hypergraph that has the property. The testability of such properties for general k-uniform hypergraphs was first shown by Alon and Shapira (for graphs) and by Rodl and Schacht (for k > 2). The query complexity time of their algorithms is enormous, growing considerably faster than a tower function. Copyright © 2015 by the Society for Industrial and Applied Mathmatics.

Actions (login required)

Edit Item