From Erdős to algorithms (Q1344623)

The probabilistic method of Paul Erdős proves the existence of an object by showing that an appropriately defined random object has a positive probability of having the desired property. This can lead to a probabilistic algorithm for creating the object. A number of instances are given in this semi-expository paper in which a weight function may be used to derandomize the algorithm, yielding a deterministic efficient algorithm to find the object.