Talk information

Date: Sunday, November 16, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Lior Gishboliner (University of Toronto)
Title: VC-dimension for hypergraphs: improved bounds

Abstract:

VC-dimension is an important notion with several applications in graph theory. A fundamental result is that graphs of bounded VC dimension have (small) homogeneous vertex-partitions, i.e., partitions where almost every pair of parts has density close to 0 or 1. Recently, Chernikov and Towsner proved a hypergraph generalization of this fact. The quantitative aspects of their result remain open. I will present some recent progress on this problem, answering two questions of Terry. This is a joint work with Asaf Shapira and Yuval Wigderson.