Probabilistic Proofs of Non-probabilistic Theorems - Combinatorics

Combinatorics

• A number of theorems stating existence of graphs (and other discrete structures) with desired properties are proved by the probabilistic method. Non-probabilistic proofs are available for some of them.

• The Maximum-minimums identity admits a probabilistic proof.