13 novembre 2017
Xavier Goaoc (Université de Marne la Vallée) En géométrie discrète et algorithmique, la complexité d'une famille d'ensemble est souvent étudiée au travers de sa fonction de pulvérisation. J'introduirai à ces fonctions et discuterai de comment leur vitesse de croissance asymptotique peut être controlée par une seule de leurs valeurs, dans l'esprit de la théorie de la "dimension de Vapnik-Chervonenkis" des hypergraphes. Je décrirai en particulier une construction probabiliste qui réfute une conjecture de Bondy et Hajnal. C'est un travail commun avec Boris Bukh (https://arxiv.org/abs/1701.06632). L'exposé ne supposera pas de connaissance particulière.
