Algorithms, Combinatorics and Optimization Seminar

Thursday, September 16, 2021 - 3:30pm to 4:30pm


In Person Wean Hall 8220


PATRICK BENNETT, Associate Professor

Random greedy independent sets and matchings in some sparse hypergraphs of high girth

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.

Patrick Bennett is an Associate Professor at Western Michigan University.  His research focuses on probabilistic combinatorics and its applications, especially to extremal combinatorics. In particular, he often analyzse random greedy algorithms on discrete structures such as hypergraphs. He received his Ph.D. in Algorithms, Combinatorics and Optimization from Carnegie Mellon University in 2013, supervised by Tom Bohman. He then held a postdoc positon at the University of Toronto from 2013-2015, supervised by Mike Molloy. He is grateful to the Simons Foundation for supporting his research.

Event Website:

For More Information, Contact:


Seminar Series