Weak saturation on graphs and hypergraphs.
Misha Tyomkyn, Charles University Prague
video available here
Suppose a pandemic spreads on the edges of a graph G as follows. Initially a subset of edges are infected. If at any point two out of three edges forming a triangle in G are infected, the third edge becomes infected too.
Continue until no further infections are possible. What we have just described is known as the weak saturation process, and can be defined for any fixed graph H in place of a triangle. It leads to a variety of interesting questions, most importantly, what is the smallest number of initially infected edges that would guarantee every edge of G to become infected? We will survey some classical and present some new results. Joint work with Denys Bulavka and Martin Tancer.
Posted on 2021-06-20