Discrete Math Seminar: Thao Do

  • Date: 03/20/2018
  • Time: 16:00
Thao Do, MIT

University of British Columbia


Zarankiewicz's problem for semi-algebraic hypergraphs


Zarankiewicz’s problem asks for the largest possible number of edges in a graph with $n$ vertices that does not contain K_{s,t} for some fixed integers $s, t$. Recently, Fox, Pach, Sheffer, Sulk and Zahl considered this problem for semi-algebraic graphs, the ones whose vertices are points in Euclidean spaces and edges are defined by some semi-algebraic relations. They found an upper bound that only depends on the dimensions of those Euclidean spaces; this result is a vast generalization of the well-known Szemer\'edi-Trotter theorem and has many geometric applications. In this talk, we will explain this result and how to extend it to hypergraphs. Our proof uses a packing result in VC-dimension theory and the polynomial partitioning method. As an application, we find an upper bound for the number of unit d × d minors in a d × n matrix with no repeated columns.

Other Information: 

ESB 4127
Tue 20 Mar 2018, 4:00pm-5:00pm