3:30 pm, Seminar Hall
Shatter functions of geometric hypergraphs
Université Paris-Est Marne-la-Vallée.
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. The talk will start from first principles.