On the power of random greedy algorithms

DOI10.1016/j.ejc.2022.103551zbMath1491.05111arXiv2104.07854OpenAlexW3153696349MaRDI QIDQ2145759

He Guo, Lutz Warnke

Publication date: 20 June 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

probabilistic methodalgorithmic approach

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

Bounds on Ramsey games via alterations, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• How to make a graph bipartite
• The early evolution of the \(H\)-free process
• The triangle-free process
• On a packing and covering problem
• Asymptotically good list-colorings
• Differential equations for random processes and random graphs
• Dense induced bipartite subgraphs in triangle-free graphs
• A subexponential upper bound for van der Waerden numbers \(W(3,k)\)
• Packing nearly optimal Ramsey \(R(3,t)\) graphs
• Bipartite induced density in triangle-free graphs
• On a conjecture of Erdős on locally sparse Steiner triple systems
• A lower bound for off-diagonal van der Waerden numbers
• On the missing log in upper tail estimates
• A note on the random greedy independent set algorithm
• The Final Size of the $C_{\ell}$-free Process
• A Note on Elkin’s Improvement of Behrend’s Construction
• Asymptotic packing via a branching process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)
• Large girth approximate Steiner triple systems
• Separation Choosability and Dense Bipartite Induced Subgraphs
• When does the K₄‐free process stop?
• The C_ℓ‐free process
• Arithmetic progressions in sumsets
• A new proof of Szemerédi's theorem
• Dynamic concentration of the triangle‐free process