Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring
Peter Maxwell Davies · Society for Industrial and Applied Mathematics eBooks · 2023
The Lovász Local Lemma is a classic result in probability theory that is often used to prove the existence of combinatorial objects via the probabilistic method. In its simplest form, it states that if we have n 'bad events', each of which occurs with probability at most p and is independent of all but d other events, then under certain criteria on p and d, all of the bad events can be avoided with positive probability.