Shatter functions of (geometric) hypergraphs

Xavier Goaoc

Université Paris-Est, Marne-la-Vallée, France

Université Paris-Est, Marne-la-Vallée, France

2017/09/25

*Mon*4PM-5PM (Room**3433**, Bldg. E6-1)In combinatorial and computational geometry, the complexity of a 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 notion of “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.

Tags: XavierGoaoc