moteur de recherche

Séminaire Algo - Xavier Goaoc
Séminaire Algo - Xavier Goaoc
10-oct.-2017 14:30
Il y a: 8 days





Xavier Goaoc

Fonctions de pulvérisation d'hypergraphes (géométriques) / Shatter functions of (geometric) hypergraphs

Salle de séminaire (4B05R) - Bâtiment Copernic

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 contrôlé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. --- In combinatorial and computational geometry, the complexity of system of sets is often studied via its shatter function. I will introduce these functions, and discuss how their asymptotic growth rate is governed from a single of its values, in the spirit of the classical "Vapnik-Chernonenkis dimension" of hypergraphs. In particular, I will describe a probabilistic construction that refutes a conjecture of Bondy and Hajnal. This is joint work with Boris Bukh (https://arxiv.org/abs/1701.06632). The talk will start from first principles.








<- retour: