Discrete Analysis Seminar

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. Using polynomial partitioning among other tools, Fox, Pach, Sheffer, Suk, and Zahl established that semialgebraic graphs enjoy stronger bounds than the usual Kovari-Sos-Turan bounds for general graphs; this provides 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).