Density and regularity theorems for semi-algebraic hypergraphs
Jacob Fox, János Pach, Andrew Suk · 2014
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 k-tuples {p1, …, pk} ⊂ P such that (p1, …, pk) ∊ 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 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 P1, …, Pk of every k-partite k-uniform semi-algebraic hypergraph H = (P1 ∪ … ∪ Pk, E) with |E| ≥ εΠkj=1|Pi| have, for 1 ≤ i ≤ k, δ|Pi|-element subsets P′i ⊆ Pi satisfying P′1 × … × P′k ⊆ 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 Bárány and Valtr: Any disjoint finite sets P1, …, Pk ⊂ ℝd (k > d) have for 1 ≤ i ≤ k subsets P′i of size at least 2−O(d3k log k)|Pi| with the property that every k-tuple formed by taking one point from each P′i has the same order type. The above techniques carry over to property testing. We show that for any typical hereditary hypergraph property , there is a randomized algorithm with query complexity ) to determine (with probability at least .99) whether a k-uniform semi-algebraic hypergraph H = (P,E) with constant description complexity is ε-near to having property , 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 Rödl and Schacht (for k > 2). The query complexity time of their algorithms is enormous, growing considerably faster than a tower function.