Discrete Math Seminar: Thao Do

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.