Probabilistic method

Summary

The probabilistic method proves that an object with a given property exists. It chooses an object at random and shows that it has the property with positive probability. It is a nonconstructive method: it usually gives no explicit example. Erdős made it a main tool of combinatorics, starting with lower bounds for Ramsey numbers. Its tools include linearity of expectation and Boole's inequality. More refined tools are the Lovász local lemma and concentration inequalities.