skip to main content
Caltech

Discrete Analysis Seminar

Tuesday, October 19, 2021
3:00pm to 4:00pm
Add to Cal
Linde Hall 187
Point-box incidences and logarithmic density of semilinear graphs
Minh Tran, Department of Mathematics, University of Notre Dame,

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).

For more information, please contact Math Department by phone at 626-395-4335 or by email at [email protected].