Jonathan Tidor: Semialgebraic graphs and polynomial partitioning

NYU CG seminar, 11/11/25. A semialgebraic graph is a graph whose vertices are points in Euclidean space and whose edge relation is defined by polynomial inequalities on the vertices. Numerous problems in discrete geometry can be encoded by a semialgebraic graph. These include the Erdős unit distance problem and its variants, incidence problems involving algebraic and semialgebraic objects, and many more. I will discuss a number of new structural and extremal results for semialgebraic graphs and some geometric consequences of these results. These include a very strong regularity lemma with optimal quantitative bounds as well as progress on the semialgebraic Zarankiewicz problem. These results are proved using a novel extension of the polynomial partitioning machinery of Guth–Katz and of Walsh. Based on joint work with Hung-Hsun Hans Yu.