3:30 pm, Seminar Hall Shatter functions of geometric hypergraphs Xavier Goaoc Université Paris-Est Marne-la-Vallée. 25-01-18 Abstract 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.
|