To content
Department of Com­pu­ter Science

Time: Usually weekly Tuesday 16:00 CET

Access: Online via Zoom Link

Upcoming talks:

  • 31st March: Fabian Burghart: “Sharp thresholds and hitting times for factors in random graphs”
    Abstract:
    Let F be a graph on r vertices and let G be a graph on n vertices. An F-factor in G is a subgraph of G composed of n/r vertex-disjoint copies of F, if r divides n. For instance, a K_2-factor is simply a perfect matching. The study of threshold functions for F-factors in G(n,p) goes back to Erdős and Rényi themselves; but for general F it was not until the 2008 breakthrough paper by Johansson, Kahn and Vu that the weak threshold for strictly 1-balanced F was established. More recently, Riordan and Heckel obtained sharp thresholds for F=K_r  and so-called nice graphs, using sophisticated coupling arguments that utilize Kahn's recent celebrated solution of Shamir's problem on hypergraph matchings. This talk reviews these results and extends them to sharp thresholds for any strictly 1-balanced F. In particular, this confirms the thirty year old conjecture by Ruciński that the sharp threshold for the emergence of an F-factor coincides with the sharp threshold for the disappearance of the last vertex that is not contained in a copy of F. These results were obtained in joint work with A. Heckel, M. Kaufmann, N. Müller, and M. Pasch.
  • 21th April: Justin Ko, Yernur Begaliyev
  • 29th April: Bill Helton
  • 5th May: Zhifei Yan
  • 12th May: Arnab Sen
  • 19th May: Kostas Panagiotou
  • 26th May: Rodrigo Veiga
  • 2nd June: Summer School - no talk
  • 9th June: Zachar Zabluchko
  • 16th June: Marcus Michelen
  • 23rd June: Sandra Kiefer
  • 30th June: Natalie Behague

ADYN seminar: Link