Probabilistic combinatorics front page

Quick description

Probabilistic combinatorics has two rather distinct flavours. The first is the study of the typical behaviour of random combinatorial objects, such as a graph with $n$ vertices where each edge is chosen randomly and independently with probability $p$ . The second is the use of random constructions to prove statements that do not mention probability, a classic example being Erdős's proof that the Ramsey number $R(k,k)$ is at least $2^{k/2}$ (which is Example 2 in the article on averaging arguments or Example 1 on the use of the probabilistic method). This page contains links to several articles: some are general articles about the probabilistic method, while others are about particular methods that have been developed to estimate probabilities in situations where they are hard to determine.

The use of the probabilistic method

What is the probabilistic method and when can it be applied? Brief summary ( This article discusses a few well-known and relatively straightforward applications of the probabilistic method, and attempts to explain how to recognise situations where the probabilistic method can be used. Many applications of the probabilistic methods require one to prove highly non-trivial estimates for probabilities: methods for obtaining such estimates are discussed in other articles (see below). )

Useful heuristic principles for guessing probabilistic estimates Brief summary ( If you are hoping to use the probabilistic method as part of a long and complicated proof, you will probably want to begin by producing a plausible sketch of the argument before you go into the technical details. For this purpose it is very useful to be able to guess upper (and sometimes lower) bounds for the probabilities of various complicated events. This article discusses heuristic principles that can help one do this, and illustrates them with examples. )

Unusual choices of probability distribution Brief summary ( For many uses of the probabilistic method, it is obvious what the best way is of choosing a random structure or substructure. However, there are some applications where a non-obvious choice is what is needed.)