Title    name
2017 Discrete Math 세미나
 
  Title
  Speaker Xavier Goaoc
  Date 2017-09-25
  Host
  Place KAIST
  File  의 1 번째 Real Media 동영상입니다.   
 
Abstract : 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.