Abstract: The random greedy algorithm for finding a maximal independent set in a graph has been studied extensively in various settings in combinatorics, probability, computer science, and chemistry. The algorithm builds a maximal independent set by inspecting the graph’s vertices one at a time according to a random order, adding the current vertex to the independent set if it is not connected to any previously added vertex by an edge.

In this talk, I will present a simple yet general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a valuable notion of local convergence. I will demonstrate the applicability of this framework by giving short and straightforward proofs for results on previously studied families of graphs, such as paths and various random graphs, and by providing new results for other models such as random trees.

If time allows, I will discuss a more delicate (and combinatorial) result, according to which, in expectation, the cardinality of a random greedy independent set in the path is no larger than that in any other tree of the same order.

The talk is based on joint work with Michael Krivelevich, Tamás Mészáros and Clara Shikhelman.