Algorithms, Combinatorics and Optimization Seminar

  • Associate Professor
  • Department of Mathematics
  • Western Michigan University

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.

For More Information, Please Contact: