Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Tuesday, November 26, 2013, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Hafsteinn Einarsson

Controlled Explosions: Restraining Bootstrap Percolation

Bootstrap Percolation is a process which simulates spread of activity in a graph. The process starts with some vertices being active (bootstrap) and follows a rule to determine which vertices will as a result turn active.

This process has been studied on various graph classes, with various rules to determine how a vertex turns active. We build on a result by Janson, Łuczak, Turova and Vallier. They proved that for G(n,p), if a vertices are initially active and if a vertex turns active if it has at least k active neighbors for some constant k, then the process will either activate all vertices or fewer than 2a vertices a.a.s.

This all-or-nothing behavior is prevalent in the study of bootstrap percolation. Inspired by biological neural networks we decided to study if this activity explosion could be controlled. First we extended the process from above by introducing inhibitory vertices and changing the rule such that a vertex turns active if it has k more excitatory than inhibitory neighbors. Second, we further extend the process by introducing a random delay on every edge in the graph.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login