Probabilistic Methods in Combinatorics

At first glance, probability and combinatorics seem like opposing forces—one deals with randomness and chance, while the other deals with precise counting and structure. The profound insight of probabilistic methods is that we can use randomness as a tool to prove the definite existence of combinatorial objects with desired properties, often without constructing a single example. This non-constructive approach has revolutionized fields like graph theory, Ramsey theory, and coding theory, providing some of the best-known bounds for fundamental problems. Mastering these methods shifts your problem-solving perspective, allowing you to demonstrate that something exists by showing that the probability of it existing is greater than zero.

The Basic Probabilistic Method

The foundational principle is elegantly simple: if you can show that a randomly chosen object from a class has a positive probability of possessing a certain property, then at least one object with that property must exist. The most common form of this argument uses expected value or the "first moment method."

Formally, let $X$ be a random variable that counts the number of "bad" features in a random structure. If you can show that the expected value $E[X]<1$, then there must be some outcome for which $X=0$. Why? Expectation is an average. If the average number of bad features is less than one, it is impossible for every outcome to have one or more bad features; at least one outcome must have zero.

Application: Lower Bounds for Ramsey Numbers A classic application is providing lower bounds for Ramsey numbers $R(k,k)$, which is the smallest number $n$ such that any two-coloring of the edges of the complete graph $K_n$ must contain a monochromatic $K_k$. Proving that $R(k,k)>n$ simply requires showing there exists a two-coloring of $K_n$ with no monochromatic $K_k$.

Consider a random coloring where each edge is colored red or blue independently with probability $1/2$. For any fixed set $S$ of $k$ vertices, let $A_S$ be the event that the clique on $S$ is monochromatic. The probability of this is $P(A_S)=2\cdot (1/2{)}^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}=2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$.

Let $X$ be the number of monochromatic $k$-cliques. By linearity of expectation, the expected number is: $$E[X]=\sum _{S}P(A_S)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}.$$

If we can choose an $n$ such that $E[X]<1$, then there exists a coloring with zero monochromatic $k$-cliques, proving $R(k,k)>n$. With careful asymptotic analysis, this yields the famous lower bound $R(k,k)>(1+o(1))\frac{k}{e\sqrt{2}}{2}^{k/2}$. The power of the method is clear: we proved the existence of an immensely complex object without ever describing it concretely.

The Second Moment Method and Threshold Phenomena

The first moment method often gives weak bounds because a low average doesn't rule out the possibility that $X$ is usually zero but occasionally enormous. The second moment method refines this by controlling the variance. It is based on Chebyshev's inequality: if $E[X]>0$ and the variance $\text{Var}(X)$ is small relative to $(E[X]{)}^2$, then $X$ is positive with high probability.

Specifically, if $E[X]\to \infty$ and $\text{Var}(X)=o((E[X]{)}^2)$, then one can show $P(X>0)\to 1$. This is crucial for proving "threshold" behavior in random graphs. For example, consider the property that a random graph $G(n,p)$ (where each edge appears independently with probability $p$) contains a copy of a fixed subgraph $H$. The second moment method can be used to prove that there is a sharp probability $p_c(n)$ such that if $p$ is slightly above $p_c$, the graph almost surely contains $H$, and if $p$ is slightly below, it almost surely does not.

The key challenge is computing $\text{Var}(X)=E[X^2]-(E[X]{)}^2$, which involves analyzing the dependence between the appearances of different copies of $H$. When these dependencies are sufficiently weak, the variance is small, and the existence threshold is established.

Alteration: Refining a Random Object

Sometimes, a purely random object almost has the property we want, but has a few "flaws." The alteration method involves taking a random object, then deterministically modifying it to remove the flaws, thereby creating a new object with the desired property.

A canonical example is proving a lower bound for the diagonal Ramsey number $R(k,k)$ that improves on the basic method. In the random coloring, the expected number of monochromatic $k$-cliques, $E[X]$, might be large. However, from each monochromatic clique, we can remove one vertex to break it. If we remove a carefully chosen set of vertices that intersects all monochromatic cliques, we are left with a smaller graph that has none. The art is to show that the number of vertices we need to remove is small, so the remaining graph is still of a size that improves the bound.

This technique bridges non-constructive and constructive proof: randomness provides a good starting point, and a deterministic cleanup phase finishes the job. It is widely used in problems related to graph coloring, independence number, and hypergraph problems where direct random sampling fails.

The Lovász Local Lemma

What if the "bad" events we want to avoid are not independent, but only "mostly" independent? The Lovász Local Lemma (LLL) is a powerful tool for such scenarios. It guarantees the existence of an object that avoids a collection of "bad" events, even when each event is highly likely, provided their dependencies are limited.

Symmetric LLL: Let $A_1,A_2,...,A_n$ be events with $P(A_i)\le p$. Each event is independent of all but at most $d$ of the others (its "dependency graph" has degree at most $d$). If $ep(d+1)\le 1$, then $P(\bigcap \overline{A_i})>0$. That is, there is a non-zero probability that none of the bad events occur.

Application: Edge Coloring of Graphs Consider the problem of coloring the edges of a graph with a limited number of colors so that no vertex has two incident edges of the same color (a proper edge-coloring). The LLL can be used to prove that if the maximum degree is $\Delta$, then a proper edge-coloring exists with only about $2\Delta$ colors (later refined to $\Delta +1$ by Vizing's theorem). One defines a random coloring and lets $A_v$ be the event that vertex $v$ has a color conflict. Each event $A_v$ depends only on the edges incident to $v$ and their neighbors—a limited dependency degree $d$. By setting up the parameters correctly, the LLL conditions are satisfied, proving the existence of such a coloring.

The LLL is particularly potent for hypergraph problems, such as 2-coloring hypergraphs to avoid monochromatic edges, and for constructing graphs with large girth and large chromatic number. Modern algorithmic versions of the LLL (e.g., Moser-Tardos algorithm) make this existential proof constructive, providing efficient randomized algorithms to find the desired object.

Common Pitfalls

1. Misapplying the First Moment Method: Assuming $E[X]<1$ guarantees $X=0$ with high probability. It does not; it only guarantees there exists an outcome with $X=0$. The probability could be vanishingly small. Confusing existence with high probability is a fundamental error.

• Correction: Remember the logic: $P(X=0)>0$. Use the second moment method if you need to show $X>0$ with high probability.

1. Ignoring Dependencies in the Local Lemma: The most common error is mis-calculating the dependency degree $d$ in the LLL. An event $A$ is not independent of an event $B$ if they share any underlying random variable. Underestimating $d$ invalidates the lemma's application.

• Correction: Construct the dependency graph rigorously. Two events are adjacent if they are not independent. $d$ is the maximum degree in this graph, not just the number of "similar" events.

1. Overlooking the Alteration Step: In the alteration method, failing to account for how the cleanup phase affects the final object's other properties can break the proof. For instance, removing vertices to break monochromatic cliques might also unintentionally create new ones.

• Correction: The alteration must be defined precisely, and its impact must be bounded quantitatively. Often, a greedy algorithm works: remove one vertex from each bad structure, and show no vertex is removed too many times.

1. Treating Probability as an Algorithm: The probabilistic method is primarily an existence tool. While it often implies a randomized algorithm ("try random objects until you succeed"), the expected running time might be exponential if the success probability is tiny. Don't assume a non-constructive proof yields an efficient construction.

• Correction: Distinguish between existential proofs and constructive/algorithmic versions. The Moser-Tardos algorithm is a notable exception for the LLL.

Summary

• The probabilistic method proves the existence of combinatorial objects by showing a randomly chosen one has a positive probability of working, even if that probability is extremely small.
• The first moment method (expectation argument) is the simplest form, often used for lower bounds on Ramsey numbers by showing the expected number of bad configurations is less than one.
• The second moment method (variance analysis) strengthens this to show events happen with high probability, crucial for establishing sharp threshold phenomena in random graphs and other structures.
• The alteration method combines randomness with deterministic cleanup, refining a random object by removing a small number of flaws to achieve the desired property.
• The Lovász Local Lemma (LLL) provides a condition under which we can avoid a collection of likely but weakly dependent "bad" events, with powerful applications in graph coloring and hypergraph problems. Its modern algorithmic versions bridge the gap between existence and construction.