The ACO Seminar (2021–2022)

We analyze two random greedy processes on sparse random graphs and hypergraphs with fixed degree sequence. We analyze the matching process, which builds a set of disjoint edges one edge at a time, and then we analyze the independent process which builds an independent set of vertices one vertex at a time. Our results for these processes generalize and extend some results of Frieze, Wormald, Brightwell, Janson and Luczak. Using a recent result of Krivelevich, Mészáros, Michaeli, and Shikhelman, we extend our result on the matching process to any (deterministic) regular hypergraph of high girth. This talk is about joint work with Deepak Bal.