Answers are grounded in this paper and cite their sources.
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 Od,k((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,k(D⁻ᵈ⁽ᵏ⁻¹⁾εᵈ⁽ᵏ⁻¹⁾⁺¹Nᵏ) edges. Third, we prove a Zarankiewicz-type result for semialgebraic hypergraphs. Previously, Fox-Pach-Sheffer-Suk-Zahl showed that a Ku,u-free semialgebraic graph on N vertices has at most Od,D,u(N2d/(d+1)+o(1)) edges and Do extended this result to Ku,…,u⁽ᵏ⁾-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.
No takes yet. Share an insight, caveat, or question.
Tidor et al. (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: