Speaker: Chieu-Minh Tran

Title: Point-box incidences and logarithmic density of semilinear graphs 

Abstract: Zarankiewicz’s problem in graph theory asks to determine for each n and k the largest possible number of edges |E| in a  K_{k,k}-free bipartite graph G = (V_1, V_2; E) with |V_1|+|V_2|=n. Semialgebraic graphs enjoy stronger bounds than the usual Kovari-Sos-Turan bounds for general graphs, providing an abstract setting for the Szemerédi-Trotter theorem and related incidence bounds. We obtain even stronger bounds for semilinear graphs, demonstrate that these are close to being optimal, and apply them to show that the number of incidences between points and boxes with axis parallel sides on the plane whose incidence graph is K_{k,k}-free is almost linear. I will also discuss how these results are related to the notion of modularity in model theory. (Joint with Abdul Basit, Artem Chernikov, Sergei Starchenko, and Terence Tao).