UBC Discrete Math Seminar: Abdul Basit

  • Date: 11/17/2020
  • Time: 16:00
Abdul Basit, Iowa State University.



Point-box incidences and logarithmic density of semilinear graphs


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.

Other Information: 

Please contact the organizer here for Zoom meeting details.