UBC Discrete Math Seminar: Abdul Basit

Zarankiewicz's problem in extremal graph theory asks for the maximum number of edges in a bipartite graph on $n$ vertices which does not contain a copy of $K_{k,k}$, the complete bipartite with $k$ vertices in both classes. We will consider this question for incidence graphs of geometric objects. Significantly better bounds are known in this setting, in particular when the geometric objects are defined by systems of algebraic inequalities. We show even stronger bounds under the additional constraint that the defining inequalities are linear. We will also discuss connections of these results to combinatorial geometry and model theory. Joint work with Artem Chernikov, Sergei Starchenko, Terence Tao, and Chieu-Minh Tran.