On the power of random greedy algorithms
arXiv:2104.07854 · doi:10.1016/j.ejc.2022.103551
Abstract
In this paper we solve two problems of Esperet, Kang and Thomasse as well as Li concerning (i) induced bipartite subgraphs in triangle-free graphs and (ii) van der Waerden numbers. Each time random greedy algorithms allow us to go beyond the Lovasz Local Lemma or alteration method used in previous work, illustrating the power of the algorithmic approach to the probabilistic method.
arXiv comment14 pages; minor edits; to appear in European Journal of Combinatorics
References in corpus (12)
- The early evolution of the H-free process
- The triangle-free process and the Ramsey number
- When does the K_4-free process stop?
- On Wormald's differential equation method
- Large girth approximate Steiner triple systems
- Separation choosability and dense bipartite induced subgraphs
- The C_\ell-free process
- Packing nearly optimal Ramsey R(3,t) graphs
- On the missing log in upper tail estimates
- Prague dimension of random graphs
- The final size of the C_4-free process
- On the power of random greedy algorithms