FOCS 2025

Romain Bourneuf, est doctorant en première année dans l'équipe GO (département CombAlgo). Avec ses co-auteurs Pierre Charbit (IRIF Paris) et Stephan Thomasse (ENS Lyon), il a écrit le papier : « A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number », 
accepté dans la conférence FOCS 2025
 

Le sujet de l’article aborde la problématique ci-après exprimée.
La VC-dimension est un paramètre permettant d'estimer la complexité d'une famille de matrices binaires (ou, de manière équivalente, d'une classe de concepts ou d'une classe de graphes). Ce paramètre est central notamment en optimisation linéaire, en apprentissage, et en combinatoire. Nous poursuivons l'étude d'une généralisation par Alon, Hanneke, Holzman et Moran, et obtenons en corollaire plusieurs résultats sur le nombre chromatique des graphes denses sans grande clique. Nous prouvons également que dans chaque élection, peu importe le nombre de candidats, il est possible de choisir un petit nombre de vainqueurs tels qu'aucun autre candidat ne batte tous les vainqueurs avec une grande marge.

Lire l’article ici
 

Contacts