Tutte colloquium-Lior Gishboliner

Title:Regularity lemmas for hypergraphs of bounded VC dimension: improved bounds

Abstract:An important result at the interface of graph theory and logic 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.