Évènement

Résumé : Motivés par le désir de construire de grands ensembles indépendants dans les graphes aléatoires, Karp et Sipser ont modifié la construction gloutonne habituelle pour produire un algorithme qui produit un ensemble indépendant avec un grand cardinal, les sommets restants formants un ensemble appelé le coeur de Karp-Sipser. Lorsqu’il est exécuté sur le graphe aléatoire d’Erdös-Rényi $G(n,c/n)$, cet algorithme est optimal tant que $c < mathrm{e}$. Nous présenterons la preuve d’une conjecture physique de Bauer et Golinelli (2002) affirmant qu’à la criticité, la taille du coeur de Karp-Sipser est de l’ordre de $n^{3/5}$. En cours de route, nous mettrons en évidence les similitudes et les différences avec l’algorithme glouton habituel pour le $k$-coeur.

Basé sur des travaux communs avec Thomas Budzinski et  Nicolas Curien.