A note on the random greedy independent set algorithm

DOI10.1002/RSA.20667zbMATH Open1349.05314arXiv1308.3732OpenAlexW1755426982MaRDI QIDQ2830236FDOQ2830236

Authors: Patrick Bennett, Tom Bohman 

Publication date: 9 November 2016

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1308.3732

Recommendations

• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• Publication:4885222
• 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

zbMATH Keywords

randomized algorithmshypergraph independence numberTurán problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65)

Cites Work

• On tail probabilities for martingales
• Probability Inequalities for Sums of Bounded Random Variables
• The triangle-free process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Extremal uncrowded hypergraphs
• On uncrowded hypergraphs
• The early evolution of the \(H\)-free process
• The diamond-free process
• The Final Size of the $C_{\ell}$-free Process
• When does the \(K_{4}\)-free process stop?
• The C_ℓ‐free process
• SIR epidemics on random graphs with a fixed degree sequence
• Some Exact Results and New Asymptotics for Hypergraph Turán Numbers
• Extremal problems for sets forming Boolean algebras and complete partite hypergraphs
• Dense subgraphs in the \(H\)-free process
• No dense subgraphs appear in the triangle-free graph process
• A note on the random greedy triangle-packing algorithm
• Triangle-free subgraphs in the triangle-free process
• Random triangle removal
• Hamiltonicity of random graphs produced by 2‐processes
• The final size of the \(C_{4}\)-free process

Cited In (30)

• The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\)
• Coloring sparse hypergraphs
• Sparse hypergraphs with applications to coding theory
• The \(Q_2\)-free process in the hypercube
• The greedy independent set in a random graph with given degrees
• On randomizing two derandomized greedy algorithms
• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs
• Title not available (Why is that?)
• It is hard to know when greedy is good for finding independent sets
• On a conjecture of Erdős on locally sparse Steiner triple systems
• Independent sets in hypergraphs omitting an intersection
• A Small Maximal Sidon Set in ${\mathbb{Z}}_2^n$
• The independent neighborhoods process
• Independence number of hypergraphs under degree conditions
• On the power of random greedy algorithms
• On the random greedy \(F\)-free hypergraph process
• Title not available (Why is that?)
• A relative Szemerédi theorem
• On the intersecting family process
• A fine-grained analysis of a simple independent set algorithm
• A gentle introduction to the differential equation method and dynamic concentration
• The sum-free process
• The Game Saturation Number of a Graph
• Greedy maximal independent sets via local limits
• Enumerating matroids of fixed rank
• The matching process and independent process in random regular graphs and hypergraphs
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• Experimental and Efficient Algorithms
• A sharp threshold for bootstrap percolation in a random hypergraph

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)