Multilevel polynomial partitioning and semialgebraic hypergraphs: regularity, Tur\'an, and Zarankiewicz results

We prove three results about semialgebraic hypergraphs. First, we prove an optimal and oblivious regularity lemma. Fox-Pach-Suk proved that the class of k-uniform semialgebraic hypergraphs satisfies a very strong regularity lemma where the vertex set can be partitioned into poly (1/) pieces so that all but an -fraction of k-tuples of parts are homogeneous (either complete or empty). Our result improves the number of parts in the partition to O₃, ₊ ( (D/) ^d) where d is the dimension of the ambient space and D is a measure of the complexity of the hypergraph; additionally, the partition is oblivious to the edge set of the hypergraph. We give examples that show that the dependence on both and D is optimal. From this regularity lemma we deduce the best-known Tur\'an-type result for semialgebraic hypergraphs. We show that any such hypergraph with N vertices and Nᵏ edges contains a complete k-uniform k-partite subhypergraph with ₃, ₊ (D^-d (k-1) ^d (k-1) +1Nᵏ) edges. Third, we prove a Zarankiewicz-type result for semialgebraic hypergraphs. Previously, Fox-Pach-Sheffer-Suk-Zahl showed that a Kₔ, ₔ-free semialgebraic graph on N vertices has at most O₃, ₃, ₔ (N^2d/ (d+1) +o (1) ) edges and Do extended this result to Kₔ, , ₔ^ (k) -free semialgebraic hypergraphs. We improve upon both of these results by removing the o (1) in the exponent and making the dependence on D and u explicit and polynomial. All three of these results follow from a novel "multilevel polynomial partitioning scheme" that efficiently partitions a point set Pᵈ by low-complexity semialgebraic pieces. We prove this result using the polynomial method over varieties as developed by Walsh which extends the real polynomial partitioning technique of Guth-Katz.