Zarankiewicz’s problem for semilinear hypergraphs

Abdul Basit, Iowa State University

Date and time: 2pm (New York time), Tuesday, December 14, 2021

Place: On Zoom (details provided on the seminar mailing list)

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

No background is assumed, and the talk will be accessible to non-experts. Joint work with Artёm Chernikov, Sergei Starchenko, Terence Tao, and Chieu-Minh Tran.