2024/07/22 by Rubin, Natan · 1 citation
#05C65 #05D10 #52A35 #52C35 #52C45 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2
paper · doi:10.48550/arxiv.2407.15518
We use the polynomial method of Guth and Katz to establish stronger and \it more efficient regularity and density theorems for such k-uniform hypergraphs H=(P,E), where P is a finite point set in \mathbb Rd, and the edge set E is determined by a semi-algebraic relation of bounded description complexity. In particular, for any 0<ε≤ 1 we show that one can construct in O(nlog (1/ε)) time, an equitable partition P=U1\uplus …\uplus UK into K=O(1/εd+1+δ) subsets, for any 0<δ, so that all but ε-fraction of the k-tuples Ui1,…,Uik are \it homogeneous: we have that either Ui1×…× Uik⊆ E or (Ui1×…× Uik)∩ E=∅. If the points of P can be perturbed in a general position, the bound improves to O(1/εd+1), and the partition is attained via a \it single partitioning polynomial (albeit, at expense of a possible increase in worst-case running time). In contrast to the previous such regularity lemmas which were established by Fox, Gromov, Lafforgue, Naor, and Pach and, subsequently, Fox, Pach and Suk, our partition of P does not depend on the edge set E provided its semi-algebraic description complexity does not exceed a certain constant. As a by-product, we show that in any k-partite k-uniform hypergraph (P1\uplus…\uplus Pk,E) of bounded semi-algebraic description complexity in \mathbb Rd and with |E|≥ ε∏i=1k|Pi| edges, one can find, in expected time O(∑i=1k(|Pi|+1/ε))log (1/ε)), subsets Qi⊆ Pi of cardinality |Qi|≥ |Pi|/εd+1+δ, so that Q1×…× Qk⊆ E.