Tue, 28 Oct 2025

14:00 - 15:00
L4

Erdős–Hajnal and VC-dimension

Tung Nguyen
(University of Oxford)
Abstract

A 1977 conjecture of Erdős and Hajnal asserts that for every hereditary class of graphs not containing all graphs, every graph in the class has a polynomial-sized clique or stable set. Fox, Pach, and Suk and independently Chernikov, Starchenko, and Thomas asked whether this conjecture holds for every class of graphs of bounded VC-dimension. In joint work with Alex Scott and Paul Seymour, we resolved this question in the affirmative. The talk will introduce the Erdős–Hajnal conjecture and discuss some ideas behind the proof of the bounded VC-dimension case.

Quantifying digital habits
 Sharpe, M Bowen, M Lambiotte, R EPJ Data Science volume 14 issue 1 (30 Sep 2025)
Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
 Todeschini, A Miscouridou, X Caron, F (05 Feb 2016)
Bayesian Nonparametrics for Sparse Dynamic Networks
 Naik, C Caron, F Rousseau, J Teh, Y Palla, K (06 Jul 2016)
Modelling sparsity, heterogeneity, reciprocity and community structure in temporal interaction data
 Miscouridou, X Caron, F Teh, Y (16 Mar 2018)
Bayesian nonparametric Plackett-Luce models for the analysis of preferences for college degree programmes
 Caron, F Teh, Y Murphy, T (21 Nov 2012)
Particle MCMC for Bayesian Microwave Control
 Minvielle, P Todeschini, A Caron, F Del Moral, P (12 May 2014)
Scalable Bayesian nonparametric regression via a Plackett-Luce model for conditional ranks
 Gray-Davies, T Holmes, C Caron, F (24 Jun 2015)
Biips: Software for Bayesian Inference with Interacting Particle Systems
 Todeschini, A Caron, F Fuentes, M Legrand, P Del Moral, P (11 Dec 2014)
Sequential Dirichlet Process Mixtures of Multivariate Skew t-distributions for Model-based Clustering of Flow Cytometry Data
 Hejblum, B Alkhassim, C Gottardo, R Caron, F Thiébaut, R (14 Feb 2017)
Subscribe to