A note on the random greedy independent set algorithm1. Issue 3 (3rd August 2016)

• Record Type: Journal Article
• Authors: Bennett, Patrick; Bohman, Tom
• Is Part Of: Random structures & algorithms. Volume 49:Issue 3(2016)
• Page Start: 479
• Page End: 502
• Publication Date: 2016-08-03
• Subjects: hypergraph independence number -- randomized algorithms -- Turan problem; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20667
• Languages: English
• ISSNs: 1042-9832

Abstract

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