Departmental Colloquium
Lior Gishboliner
University of Toronto
Regularity and VC-dimension for hypergraphs: improved bounds
Abstract: Regularity and VC-dimension are two fundamental notions with many
applications in combinatorics and beyond. These notions are related via
the result that graphs of bounded VC-dimension have (small) partitions
where most pairs of parts have density close to 0 or 1. Recent work has
generalized this to hypergraphs, but the quantitative aspects of these
results are still far from fully understood. I will present some new
results on this problem. Joint work with Asaf Shapira and Yuval Wigderson.
Friday December 5, 2025 at 3:00 PM in 636 SEO