A polynomial regularity lemma for semi-algebraic hypergraphs and its applications in geometry and property testing

Fox, Jacob and Pach, János and Suk, Andrew (2016) A polynomial regularity lemma for semi-algebraic hypergraphs and its applications in geometry and property testing. SIAM JOURNAL ON COMPUTING, 45 (6). pp. 2199-2223. ISSN 0097-5397

Preview

Text 58c02b77f036fc8c54be3e6574bf55950605.pdf Download (281kB) | Preview

Abstract

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,\ldots,P_k$ of every $k$-partite $k$-uniform semialgebraic hypergraph $H=(P_1\cup\cdots\cup P_k, E)$ with $|E|\ge\varepsilon\Pi_{j=1}^k|P_i|$ have, for $1 \leq i \leq k$, $\delta|P_i|$-element subsets $P'_i\subseteq P_i$ satisfying $P_{1}'\times\cdots\times P_{k}'\subseteq 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 Bárány and Valtr: Any disjoint finite sets $P_1,\ldots,P_k\subset \mathbb{R}^d\; (k>d)$ have, for $1 \leq i \leq k$, subsets $P'_i$ of size at least $2^{-O(d^3k\log k)}|P_i|$ 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 $\varepsilon>0$ the vertex set can be equitably partitioned into a bounded number of parts (in terms of $\varepsilon$ and the complexity) so that all but an $\varepsilon$-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/\varepsilon$. 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.

Actions (login required)

Edit Item