A note on the random greedy independent set algorithm
From MaRDI portal
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 choose 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 cup {v} contains no edge of 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 ((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.
Recommendations
- Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
- scientific article; zbMATH DE number 903456
- The matching process and independent process in random regular graphs and hypergraphs
- A natural barrier in random greedy hypergraph matching
- On the random greedy F-free hypergraph process
Cites work
- A note on the random greedy triangle-packing algorithm
- Dense subgraphs in the H-free process
- Extremal problems for sets forming Boolean algebras and complete partite hypergraphs
- Extremal uncrowded hypergraphs
- Hamiltonicity of random graphs produced by 2‐processes
- No dense subgraphs appear in the triangle-free graph process
- On tail probabilities for martingales
- On uncrowded hypergraphs
- Probability Inequalities for Sums of Bounded Random Variables
- Random triangle removal
- SIR epidemics on random graphs with a fixed degree sequence
- Some Exact Results and New Asymptotics for Hypergraph Turán Numbers
- The Cℓ‐free process
- The diamond-free process
- The early evolution of the \(H\)-free process
- The Final Size of the $C_{\ell}$-free Process
- The final size of the \(C_{4}\)-free process
- The Ramsey number R(3, t) has order of magnitude t2/log t
- The triangle-free process
- Triangle-free subgraphs in the triangle-free process
- When does the \(K_{4}\)-free process stop?
Cited in
(31)- A sharp threshold for bootstrap percolation in a random hypergraph
- The matching process and independent process in random regular graphs and hypergraphs
- On the power of random greedy algorithms
- The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\)
- The \(Q_2\)-free process in the hypercube
- On a conjecture of Erdős on locally sparse Steiner triple systems
- The sum-free process
- A relative Szemerédi theorem
- A gentle introduction to the differential equation method and dynamic concentration
- Coloring sparse hypergraphs
- It is hard to know when greedy is good for finding independent sets
- A fine-grained analysis of a simple independent set algorithm
- The independent neighborhoods process
- On the random greedy \(F\)-free hypergraph process
- scientific article; zbMATH DE number 4149905 (Why is no real title available?)
- The greedy independent set in a random graph with given degrees
- scientific article; zbMATH DE number 903456 (Why is no real title available?)
- A Small Maximal Sidon Set in ${\mathbb{Z}}_2^n$
- Enumerating matroids of fixed rank
- Sparse hypergraphs with applications to coding theory
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- The Game Saturation Number of a Graph
- On randomizing two derandomized greedy algorithms
- Experimental and Efficient Algorithms
- Independent sets in hypergraphs omitting an intersection
- Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
- Independence number of hypergraphs under degree conditions
- Greedy maximal independent sets via local limits
- On the intersecting family process
- Combinatorics. Abstracts from the workshop held January 4--9, 2026
- A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs
This page was built for publication: A note on the random greedy independent set algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830236)
