Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, December 10, 2024, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Marc Kaufmann

Sharp Thresholds for Strictly 1-Balanced Graph Factors

Let F be a graph on r vertices and let G be a graph on n vertices. Then an F-factor in G is a subgraph of G composed of n/r vertex-disjoint copies of F, if r divides n. In other words, an F-factor yields a partition of the n vertices of G. In 2008, Johansson, Kahn and Vu established the thresholds for the existence of an F-factor for strictly 1-balanced F -- up to the leading constant. The sharp thresholds, meaning the leading constants, were obtained recently by Riordan and Heckel, but only for complete graphs F=Kr and for so-called nice graphs. Their results rely on beautiful couplings that utilize the solution of Shamir's problem by Kahn. We extend the couplings by Riordan and Heckel to any strictly 1-balanced F and thereby obtain the sharp threshold for the existence of an F-factor. The work I will present is joint with Fabian Burghart, 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:   2025  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