Paper Info
Title
A note on the random greedy independent set algorithm.
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-epsilon for some epsilon > 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 U {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 Omega(N . ((logN)/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. (C) 2016 Wiley Periodicals, Inc.
Year
DOI
Venue
2016
10.1002/rsa.20667
RANDOM STRUCTURES & ALGORITHMS
Keywords
Field
DocType
hypergraph independence number,randomized algorithms,Turan problem
Discrete mathematics,Randomized algorithm,Combinatorics,Vertex (geometry),Upper and lower bounds,struct,Hypergraph,Greedy algorithm,Independent set,Mathematics,Maximal independent set
Journal
Volume
Issue
ISSN
49.0
3.0
1042-9832
Citations 
PageRank 
References 
3
0.41
9
Authors
2
Name
Order
Citations
PageRank
Patrick Bennett151.89
Tom Bohman225033.01