Lior Gishboliner : Regularity and VC-dimension for hypergraphs: improved bounds

Posted by Dhruv Mubayi , part of the Departmental Colloquium.

At

Dec. 5, 2025, 3 p.m.

In

636 SEO

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.