Mardi 14 Mars

Heure:	14:00 - 17:00
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Géométrie combinatoire : densité d'hypergraphes et méthode probabiliste
Description:	Xavier Goaoc Un hypergraphe à n sommets dont aucune projection sur k sommet n'est complète a au plus O(n^{k-1}) arêtes. Ce résultat, découvert simultanément par Sauer, Vapnick-Chervonenkis et Perles-Shelah au début des années 1970, est fondamental en apprentissage. En géométrie combinatoire et algorithmique, il permet souvent de contrôler la complexité (globale) d'une structure par sa "densité" locale. J'introduirai à ce mécanisme avant de présenter quelques extensions récentes, obtenues conjointement avec Boris Bukh (https://arxiv.org/abs/1701.06632), qui permettent un controle plus fin de la complexité. L'exposé ne supposera aucune connaissance préalable et un des ingrédients sera une construction probabiliste.