 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

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

 Mittagsseminar Talk Information

Date and Time: Tuesday, October 13, 2015, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Christoph Koch (TU Graz)

## Bootstrap percolation on random hypergraphs

Bootstrap percolation with activation parameter $r>1$ is a deterministic "infection" process on a hypergraph evolving in rounds: Initially some subset of vertices is infected. Subsequently in each round the infection spreads to all uninfected vertices with at least $r$ infected neighbours. Once a vertex becomes infected, it remains so forever.

In this talk we consider bootstrap percolation on the binomial random $k$-uniform hypergraph $H^k(n,p)$, whose vertex set is $\{1,\dots,n\}$ and where each edge consists of precisely $k$ distinct vertices and is present with probability $p$ independently. The main question is whether the infection can spread from a small set of initially infected vertices to almost all vertices. We determine the exact threshold for this property with respect to the number of initially infected vertices in the regime $n^{-1}\ll p\ll n^{-1/r}$, i.e. a threshold function $a_c=a_c(r,n,p)$ such that for any constant $\varepsilon>0$ with probability tending to $1$ as $n\to\infty$ the following two properties hold: Infecting at most $(1-\varepsilon)a_c$ vertices initially leads to no significant spread of the infection; While an initial infection of at least $(1+\varepsilon)a_c$ vertices suffices to spread the infection to almost all vertices.

This extends a result by Janson, T. Luczak, Turova and Vallier concerning the graph case $k=2$.

Joint work with Mihyun Kang and Tamas Makai.

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

Information for students and suggested topics for student talks