A note on the random greedy independent set algorithm

Let r be a fixed constant and let H be an r ‐uniform, D ‐regular hypergraph on N vertices. Assume further that D > N ϵfor some ϵ > 0 . Consider the random greedy algorithm for forming an independent set in H . An independent set is chosen at random by iteratively choosing vertices at random to be in the independent set. At each step we chose a vertex uniformly at random from the collection of vertices that could be added to the independent set (i.e. the collection of vertices v with the property that v is not in the current independent set I and I ∪ { v } contains no edge in H ). Note that this process terminates at a maximal subset of vertices with the property that this set contains no edge of H ; that is, the process terminates at a maximal independent set. We prove that if H satisfies certain degree and codegree conditions then there are Ω ( N · ( ( log N ) / D )1 r − 1)vertices in the independent set produced by the random greedy algorithm with high probability. This result generalizes a lower bound on the number of steps in the H ‐free process due to Bohman and Keevash and produces objects of interest in additive combinatorics. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 479–502, 2016