Atlanta Combinatorics Colloquium
Jointly hosted by: GT School of Mathematics, Georgia State University, and Emory University
Event & Location
Talk: 4:00 PM – 5:00 PM @ Skiles 005
Reception: 3:30 PM
Title: Random Graph Processes
Lecture Abstract
Fix a graph or uniform hypergraph F and consider the following simple process. Start with the complete (hyper)graph Kn on n vertices and repeatedly remove the edge set of a copy of F, chosen uniformly at random among all copies present at that time. Stop when no copy of F is left. This is the F-removal process, and the key question is when it ends, that is, how many edges are left at the end.
This question has proven to be very hard. In 2015, Bohman, Frieze and Lubetzky famously proved that the triangle-removal process typically ends with n^(3/2+o(1)) edges. Until now, the answer was not known for any other F.
We determine when the F-removal process ends for many choices of F. This includes cliques, where it confirms a well-known conjecture of Bennett and Bohman on the final number of edges. This is joint work with Kühn.
About the Speaker
Felix Joos has been a full professor for discrete mathematics and theoretical computer science at Heidelberg University, Germany since 2024. He received a PhD from the University of Ulm in 2015 and was a postdoc at the University of Birmingham, UK until 2019. He joined Heidelberg University as an assistant professor in 2020. He works in extremal and probabilistic combinatorics, especially on graph decompositions, hypergraph matchings, and random constructions. He is one of the recipients of the European Prize in Combinatorics 2023.