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

Date and Time: Tuesday, November 01, 2022, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Marc Kaufmann

Hitting time of clique factors in the random graph process

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.

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

Previous talks by year:   2024  2023  2022  2021  2020  2019  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