A note on the random greedy independent set algorithm1. Issue 3 (3rd August 2016) - Bennett, Patrick; Bohman, Tom
Abstract : 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