Probabilistic method

In mathematics, the probabilistic method is a special way to prove that certain mathematical objects exist. This method was started by a famous mathematician named Paul Erdős. It works by picking objects randomly and showing that there is a chance—more than zero—that the chosen object has the exact properties we are looking for. Even though we use probability in the proof, the result is certain and without any doubt.

This powerful method is mainly used in combinatorics, which is the study of how things can be combined. But it has also been used in many other areas of math, like number theory, linear algebra, and real analysis. Beyond math, it helps in computer science, for example in a technique called randomized rounding, and even in information theory. This means the probabilistic method is a useful tool in many different fields, helping scientists and mathematicians discover new truths.

Introduction

The probabilistic method is a way to prove that certain things exist by using probability. If we can show that the chance of picking an object with a special property is more than zero, then we know such an object must exist. This method was pioneered by mathematician Paul Erdős.

Another use of this method is to look at the average, or expected value, of a random result. By studying this average, we can prove that some results must be higher or lower than the average. Tools like Markov's inequality, the Chernoff bound, and the Lovász local lemma are often used in these proofs.

Two examples due to Erdős

Many famous proofs using the probabilistic method were created by Paul Erdős. One example from 1947 shows how to prove a lower bound for a number called the Ramsey number. This means we can show that for smaller enough groups of points, we can color the lines between them red or blue so that no group of points all connected by the same color exists.

Another example from 1959 asks whether we can create a network where all loops are long enough, and still need many colors to color each point differently. By looking at large random networks, we can show this is possible. This helps explain why finding the minimum number of colors for a network can be very hard, even without obvious reasons like small loops.

theorems tournaments Hamiltonian cycles Ramsey number complete graph vertices edges subgraph subsets expected value integer open graph theory chromatic number Markov's inequality independent set