Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 01, 2022, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Marc Kaufmann
Given a graph G=(V,E) on n vertices, a clique factor, for a fixed clique size r, is a cover of V by n/r pair-wise disjoint cliques contained in E. When does a clique factor emerge in the random graph process? A related question, known as "Shamir's problem" (1979) asks when the random r-uniform hypergraph contains a perfect matching. Jeff Kahn (2019) determined the sharp threshold answer for the latter. Using elegant coupling arguments, Oliver Riordan (2018) and Annika Heckel (2021) extended this to a sharp-threshold result concerning clique factors in G(n,p). For perfect matchings in r-uniform hypergraphs, as shown by Kahn (2020), even more is true: Order all possible hyperedges uniformly at random and insert them one by one. As soon as the last isolated vertex joins a hyperedge, the hypergraph contains a perfect matching. We establish the analogous hitting time result for clique factors in the random graph process: When the last vertex joins a clique of size r, the stopped random graph contains a clique factor with high probability. This is joint work with Annika Heckel, Noela Müller and Matija Pasch.
Automatic MiSe System Software Version 1.4803M | admin login