Xavier Goaoc, Shatter functions of (geometric) hypergraphs

Shatter functions of (geometric) hypergraphs
Xavier Goaoc
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.


Comments are closed.