“Having a paper accepted by this conference means that leading international experts have recognized our work as original, rigorous, and a significant step forward,” says Romain Bourneuf. “For us, this is a tremendous scientific achievement and a great source of motivation.”

The paper, titled “A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number,” explores a central concept in machine learning and its applications in a seemingly very distant field, combinatorics, as Romain Bourneuf explains in the abstract of his paper.

“The VC-dimension is a concept that allows us to measure, in a way, the ‘complexity’ of a family of mathematical objects, such as sets, graphs, or functions. This notion was introduced into the field of machine learning to estimate how many examples are needed to train an artificial intelligence model.

In this article, we study a generalization of this concept and deepen our theoretical understanding of it. This allows us to derive several applications in various areas of combinatorics. Thus, on the one hand, we obtain surprisingly simple proofs of certain already known but complex results, and on the other hand, we establish new results. For example, we show that in any election where voters rank all candidates, it is possible to select a small group of ‘winners’ such that no other candidate is significantly preferred over all the winners.

In conclusion, this work illustrates how ideas from machine learning can be applied to problems in combinatorics, opening up new avenues for research.”

Reference: “A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number”
DOI: https://arxiv.org/abs/2504.02992

FOCS Conference