## 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, April 30, 2015, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Dániel Korándi

Given a random 3-uniform hypergraph $H=H(n,p)$ on $n$ vertices where each triple independently appears with probability $p$, consider the following graph process. We start with the star $G_0$ on the same vertex set, containing all the edges incident to some vertex $v_0$, and repeatedly add an edge $xy$ if there is a vertex $z$ such that $xz$ and $zy$ are already in the graph and $xzy \in H$. We say that the process propagates if it reaches the complete graph before it terminates. In this talk we show that the threshold probability for propagation is $p=1/2\sqrt{n}$ using the differential equation method. As an application, we obtain the upper bound $p=1/2\sqrt{n}$ on the threshold probability that a random 2-dimensional simplicial complex is simply connected.

Joint work with Yuval Peled and Benny Sudakov

Information for students and suggested topics for student talks