기초과학VOD

BASIC SCI VOD

  •   >  
  • 연구동향
  •   >  
  • 기초과학VOD
Super Title 2017 Discrete Math 세미나
Title The Best Way to Spread a Rumour in a High-Dimensional Grid
Speaker Noel Jonathan  (  University of Warwick, UK  ) Date 2017-11-14
Host KAIST Place KAIST
VOD    
Bootstrap percolation is a simple process which is used as a model of propagation phenomena in real world networks including, for example, the spread of a rumour in a social network, the dynamics of ferromagnetism and information processing in neural networks. Given a graph G and an integer r, the r-neighbour bootstrap process begins with a set of “infected” vertices and, in each step, a “healthy” vertex becomes infected if it has at least r infected neighbours. A central problem in the area is to determine the size of the smallest initial infection which will spread to every vertex of the graph. In this talk, I will present a trick for obtaining lower bounds on this quantity by transforming the problem into an infection problem on the edges of the graph and applying some basic facts from linear algebra. In particular, I will outline a proof of a conjecture of Balogh and Bollobás (2006) on the smallest infection which spreads to every vertex of a high-dimensional square lattice and mention some potential applications to analysing the behaviour of a random infection in this setting. This talk is based on joint work with Natasha Morrison.

이 페이지에서 제공하는 정보에 만족하십니까?