Introduction to Ramsey Theory: Students' Projects

Subsection 14.3.1 Jay Cummings's favourite proof

The probabilistic method is a non-constructive approach in combinatorics and mathematics at large, pioneered by Paul Erdős in the mid–20th century. It is a technique used to prove the existence of a mathematical object that meets a certain condition by showing that, if objects are randomly selected from a set in a certain way, the probability of selecting an object that does not meet the condition is less than one. Since probabilities are real numbers between 0 and 1, showing that the probability of failure is less than one implies that there must be at least one success, which proves the existence of an object that satisfies the condition. Here's an outline of how the probabilistic method works:

1. Define the Universe: Identify the universe of all possible objects or configurations under consideration.

2. Choose a Probability Distribution: Select a suitable probability distribution to randomly choose an object or configuration from this universe.

3. Calculate Probabilities: Calculate the probability that a randomly chosen object fails to meet the desired property or condition.

4. Apply the Principle of Probabilistic Existence: If the calculated probability of failure is less than one, conclude that there must exist at least one object with the desired property (since if all objects failed to meet the property, the probability of failure would be one).

5. Non-Constructive Nature: Often, this method doesn't give a specific example of the object; it just proves its existence. Hence, it's considered non-constructive.

6. Extensions: The method can be extended with additional techniques like the linearity of expectation, the Local Lemma, and concentration inequalities to handle more complex problems and scenarios.

7. Applications: The probabilistic method has broad applications across graph theory, number theory, computer science (particularly in algorithms and complexity), and combinatorics.

One of the classic applications of the probabilistic method is in proving the existence of graph structures with certain properties, such as the existence of graphs with high girth and high chromatic number. The method can also show the existence of subsets of integers with specific sum properties, or the existence of solutions to certain combinatorial problems. [14.3.3.1]

Subsection 14.3.2 Reflection

Cumming's preference for the probabilistic method as a proof technique reflects a blend of theoretical rigour and practicality in mathematics, illustrating the power of probability in establishing the existence of mathematical constructs without necessarily constructing them. We learned in the class that Paul Erdős was both a frequent user an a promoter of the probabilistic method.