FOCS 2025

Romain Bourneuf is a first-year doctoral student in the GO team (CombAlgo department). With co-authors Pierre Charbit (IRIF Paris) and Stephan Thomasse (ENS Lyon), he wrote the paper: “A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number”, accepted at the FOCS 2025 conference


 

The subject of this article is the following problem.
The VC-dimension is a parameter for estimating the complexity of a family of binary matrices (or, equivalently, of a class of concepts or a class of graphs). This parameter is central to linear optimization, learning and combinatorics. We continue the study of a generalization by Alon, Hanneke, Holzman and Moran, and obtain as a corollary several results on the chromatic number of dense graphs without a large clique. We also prove that in every election, no matter how many candidates there are, it is possible to choose a small number of winners such that no other candidate beats all the winners by a large margin.


Read the article here
 

Contacts