Geometry Seminar
SPECIAL EVENT: An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs
Speaker: Natan Rubin, Ben-Gurion University
Location: Warren Weaver Hall 1314 in person and on Zoom
Date: Thursday, January 16, 2025, 12:30 p.m.
Synopsis:
The vast majority of hypergraphs that arise in discrete and computational geometry, describe semi-algebraic relations between elementary geometric objects. We use the polynomial method of Guth and Katz to establish stronger and more algorithmically efficient regularity and density theorems for such \(k\)-uniform hypergraphs \(H=(P,E)\), where \(P\) is a finite point set in \(\mathbb{R}^d\), and the edge set \(E\) is determined by a semi-algebraic relation of bounded description complexity.
In particular, for any \(0<\epsilon\leq 1\) we show that one can construct in expected\(O\left(n\log (1/\epsilon\right))\) time, an equitable partition \(P=U_1\uplus \ldots\uplus U_K\) into \(K=O(1/\epsilon^{d+1+\delta})\) subsets, for any \(0<\delta\), so that all but \(\epsilon\)-fraction of the \(k\)-tuples \(U_{i_1},\ldots,U_{i_k}\) are homogeneous: we have that either \(U_{i_1}\times\ldots\times U_{i_k}\subseteq E\) or \((U_{i_1}\times\ldots\times U_{i_k})\cap E=\emptyset\). If the points of \(P\)can be perturbed into a general position, the bound improves to \(O(1/\epsilon^{d+1})\), and the partition is attained via a single partitioning polynomial (albeit, at expense of a possible increase in the worst-case running time).
The best previously known such partition, due to Fox, Pach and Suk [SIAM. J. Comput. 2016] requires \(\Omega\left(n^{k-1}/\epsilon^{c}\right)\) time and yields \(K=1/\epsilon^c\) parts (for \(0<\epsilon\leq 1/4\)), where \(c\) is an enormous constant which is not stated explicitly and depends not only on the dimension \(d\) but also on the semi-algebraic description complexity of the hypergraph.
In contrast to the previous such regularity lemmas which were established by Fox, Gromov, Lafforgue, Naor, and Pach [J. Reine Angew. Math. 2012] 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.
Notes:
In person and simultaneously Zoom-broadcast at the usual place. Contact Boris Aronov to be put on the mailing list and/or get access to the physical location if you are not NYU-affiliated.