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.

Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
 Todeschini, A Miscouridou, X Caron, F (05 Feb 2016) doi:10.48550/arxiv.1602.02114
Modelling sparsity, heterogeneity, reciprocity and community structure in temporal interaction data
 Miscouridou, X Caron, F Teh, Y (16 Mar 2018) doi:10.48550/arxiv.1803.06070
Bayesian nonparametric Plackett-Luce models for the analysis of preferences for college degree programmes
 Caron, F Teh, Y Murphy, T (21 Nov 2012) doi:10.48550/arxiv.1211.5037
Scalable Bayesian nonparametric regression via a Plackett-Luce model for conditional ranks
 Gray-Davies, T Holmes, C Caron, F (24 Jun 2015) doi:10.48550/arxiv.1506.07412
Biips: Software for Bayesian Inference with Interacting Particle Systems
 Todeschini, A Caron, F Fuentes, M Legrand, P Del Moral, P (11 Dec 2014) doi:10.48550/arxiv.1412.3779
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) doi:10.48550/arxiv.1702.04407
Subscribe to