Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

Mittagsseminar Talk Information

Date and Time: Thursday, June 18, 2015, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Felix Weissenberger

Bootstrap Percolation with Inhibition: the Role of Edge Delays

We study bootstrap percolation on a random graph where each vertex is either excitatory or inhibitory and the information of having an active neighbour needs a certain time (delay) to be delivered: initially a subset of the vertices is activated; thereafter, a vertex gets active when it knows that it has k more excitatory than inhibitory active neighbours and stays active forever.

It is known that for deterministic delays of length 1 the size of the final active set is unstable in the size of the starting set (instability) and that exponentially distributed delays lead to a final active set whose size is independent of the size of the starting set (normalization).

We discuss the behaviour for more general delay distributions and show that the above cases are generic, i.e., all “tame” delay distributions lead to one of the two behaviours, either to instability or to normalization.

Joint work with Johannes Lengler and Angelika Steger


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

Previous talks by year:   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