A note on the random greedy independent set algorithm

DOI10.1002/RSA.20667MaRDI QIDQ2830236zbMATH OpenOpenAlexFDO

Authors Patrick Bennett, Tom Bohman

Publication date 9 November 2016

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

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

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)

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
• 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

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 Final Size of the $C_{\ell}$-free Process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The diamond-free process
• The early evolution of the \(H\)-free process
• The final size of the \(C_{4}\)-free process
• The triangle-free process
• Triangle-free subgraphs in the triangle-free process
• When does the \(K_{4}\)-free process stop?

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
• A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs
• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• It is hard to know when greedy is good for finding independent sets
• scientific article; zbMATH DE number 903456 (Why is no real title available?)
• On a conjecture of Erdős on locally sparse Steiner triple systems
• Independent sets in hypergraphs omitting an intersection
• The independent neighborhoods process
• A Small Maximal Sidon Set in ${\mathbb{Z}}_2^n$
• Independence number of hypergraphs under degree conditions
• On the power of random greedy algorithms
• On the random greedy \(F\)-free hypergraph process
• A relative Szemerédi theorem
• scientific article; zbMATH DE number 4149905 (Why is no real title available?)
• 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
• Enumerating matroids of fixed rank
• Greedy maximal independent sets via local limits
• 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
• A sharp threshold for bootstrap percolation in a random hypergraph
• Experimental and Efficient Algorithms

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)