A note on the random greedy independent set algorithm

DOI10.1002/rsa.20667zbMath1349.05314arXiv1308.3732OpenAlexW1755426982MaRDI QIDQ2830236

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 algorithmsTurán problemhypergraph independence number

Mathematics Subject Classification ID

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

Related Items (17)

The independent neighborhoods process ⋮ On the Random Greedy $F$-Free Hypergraph Process ⋮ On the power of random greedy algorithms ⋮ A Small Maximal Sidon Set in ${\mathbb{Z}}_2^n$ ⋮ A gentle introduction to the differential equation method and dynamic concentration ⋮ Independent sets in hypergraphs omitting an intersection ⋮ Independence number of hypergraphs under degree conditions ⋮ The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\) ⋮ The \(Q_2\)-free process in the hypercube ⋮ Sparse Hypergraphs with Applications to Coding Theory ⋮ On a conjecture of Erdős on locally sparse Steiner triple systems ⋮ Enumerating matroids of fixed rank ⋮ The sum-free process ⋮ A sharp threshold for bootstrap percolation in a random hypergraph ⋮ Coloring Sparse Hypergraphs ⋮ The Game Saturation Number of a Graph ⋮ A relative Szemerédi theorem

Cites Work

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

This page was built for publication: A note on the random greedy independent set algorithm