[2017 Discrete Math 세미나 ]

** Date: ** 2017-11-14

**Speaker :** Noel Jonathan (University of Warwick, UK)

**Abstract : **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.

**VOD : **[Android_VOD] [iPhone_VOD] [Windows_VOD]

Information Center for Mathematical Sciences KAIST

305-701 대전광역시 유성구 대학로 291 (구성동373-1)

한국과학기술원(KAIST) 수리과학정보센터

전화 042-350-8195~6 / 팩스 042-350-5722

e-mail : mathnet@mathnet.or.kr

Copyright (C) 2017. ICMS All Rights Reserved.

305-701 대전광역시 유성구 대학로 291 (구성동373-1)

한국과학기술원(KAIST) 수리과학정보센터

전화 042-350-8195~6 / 팩스 042-350-5722

e-mail : mathnet@mathnet.or.kr

Copyright (C) 2017. ICMS All Rights Reserved.