##
A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of every k -partite k -uniform semialgebraic hypergraph H = (P-1 U center dot center dot center dot U P-k, E) with vertical bar E vertical bar >= epsilon ll(j=1)(k) vertical bar P-i vertical bar have, for 1 <= i <= k, delta vertical bar P-i vertical bar-element subsets P'(i) subset of P-i satisfying P'(1) x center dot center dot center dot x P'(k) subset of E. The best previously known lower bound on delta due to Bukh and Hubard decreased triple 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-1 center dot center dot center dot P-k subset of R-d (k > d) have, for 1 <= i <= k, subsets P'(i) of size at least 2(-O(d3k log k)) vertical bar P-i vertical bar with the property that every k-tuple formed by taking one point from each P'(i) has the same order type. We also improve a result of Fox, Gromov, Lafforgue, Naor, and Pach, who established a regularity lemma for semialgebraic k -uniform hypergraphs of bounded complexity, showing that for each epsilon > 0 the vertex set can be equitably partitioned into a bounded number of parts (in terms of epsilon and the complexity) so that all but an epsilon-fraction of the k-tuples of parts are homogeneous. Here, we prove that the number of parts can be taken to be polynomial in 1/epsilon. Our improved regularity lemma can be applied to geometric problems and to the following general question on property testing: is it possible to decide, with query complexity polynomial in the reciprocal of the approximation parameter, whether a hypergraph has a given hereditary property? We give an affirmative answer for testing typical hereditary properties for semialgebraic hypergraphs of bounded complexity.

Published in:

Siam Journal On Computing, 45, 6, 2199-2223

Publisher:

Philadelphia, Society for Industrial and Applied Mathematics

ISSN:

0097-5397

Keywords:

Laboratories:

Record created 2017-02-17, last modified 2018-09-13