Questions: The Probabilistic Method in Algorithm Design

Question 1

Erdos proved that R(k,k) >= 2^(k/2) using the probabilistic method. What is the argument?

Model answer: Color each edge of K_n with red or blue uniformly at random. For any set S of k vertices, the probability that S forms a monochromatic clique is 2 * 2^(-C(k,2)) = 2^(1-k(k-1)/2). By the union bound over all C(n,k) subsets of size k, the expected number of monochromatic k-cliques is C(n,k) * 2^(1-k(k-1)/2). When n = 2^(k/2), this expected count is less than 1 (since C(n,k) < n^k/k! and the exponential decay dominates). If the expected number of bad events is less than 1, there exists a coloring with zero monochromatic k-cliques. Therefore R(k,k) > 2^(k/2).

This is the first moment method in its purest form: if E[number of bad structures] < 1, a good structure exists. The argument is non-constructive — we know the coloring exists but the proof gives no way to find it efficiently. Despite 75 years of effort, the 2^(k/2) lower bound has only been improved by a constant factor (to 2^(k/2) * sqrt(2) by Sah in 2023). This is widely regarded as one of the greatest demonstrations of the probabilistic method's power.

Question 2

The alteration method improves on the basic probabilistic method by first generating a random structure and then deterministically removing defects. For the independent set problem, this yields a bound of alpha(G) >= sum_v 1/(d(v)+1). Which step is the 'alteration'?

• A. Randomly recolor vertices until the graph becomes independent
• B. Include each vertex independently with probability p, then remove one endpoint from every remaining edge — the expected surviving independent set has size n*p - m*p^2, optimized by choosing p = n/(2m)
• C. Apply the greedy algorithm to a random permutation of vertices
• D. Remove all vertices of degree above the average

Answer: (B)

The alteration method for independent sets works in two phases: (1) include each vertex independently with probability p (random phase), (2) for each edge with both endpoints included, remove one endpoint (alteration/deletion phase). The expected number of included vertices is np. The expected number of edges to fix is at most mp^2 (each edge has both endpoints included with probability p^2). After alteration, the expected independent set size is at least np - mp^2. Choosing p = n/(2m) = 1/(2*d_avg/2) optimizes this to n^2/(4m). The vertex-specific version with p_v = 1/(d(v)+1) yields alpha(G) >= sum 1/(d(v)+1) via the Turan-type bound.

Question 3

The second moment method proves that a random variable X is positive with high probability. It uses the inequality Pr[X > 0] >= (E[X])^2 / E[X^2]. This is the Paley-Zygmund inequality.

• T. True
• F. False

Answer: True

The Paley-Zygmund inequality states Pr[X > 0] >= (E[X])^2 / E[X^2] for non-negative X. Equivalently, Pr[X = 0] <= Var(X) / (E[X])^2 via Chebyshev. The second moment method works by: (1) compute E[X] to show it's large (first moment gives existence), (2) compute E[X^2] = E[X]^2 + Var(X) and show Var(X) is not too large compared to E[X]^2, (3) conclude X > 0 with positive (or even high) probability. This is strictly stronger than the first moment method — it proves concentration, not just existence. Classic applications include threshold phenomena in random graphs (e.g., proving that G(n, c/n) has a giant component for c > 1).

Question 4

The probabilistic method is inherently non-constructive: it can never lead to efficient algorithms for finding the objects whose existence it proves.

• T. True
• F. False

Answer: False

While many probabilistic method arguments are non-constructive, several can be made algorithmic. The method of conditional expectations converts any first-moment probabilistic existence proof into a deterministic polynomial-time construction by greedily fixing each random choice to maintain the conditional expectation. The Lovász Local Lemma was made constructive by Moser and Tardos (2010). Randomized algorithms directly implement probabilistic arguments — if the expected number of trials to find a good object is polynomial, the algorithm is efficient. The probabilistic method's value in algorithm design is precisely that many of its arguments CAN be made constructive.

Question 5

To prove that there exists a tournament on n vertices where every set of k = O(log n) vertices has a common dominator, the probabilistic method shows that the expected number of sets WITHOUT a dominator is less than 1. What probability space is used?

• A. Each game outcome is decided by a biased coin with p = k/n
• B. Each directed edge is oriented independently and uniformly at random (probability 1/2 each direction), making it a random tournament
• C. Vertices are randomly permuted and edges point from earlier to later
• D. A uniformly random Hamiltonian path determines all edge orientations

Answer: (B)

In a random tournament, each edge is oriented independently with probability 1/2. For a fixed set S of k vertices and a fixed vertex v outside S, the probability that v beats all of S is 2^(-k). The probability that NO vertex outside S dominates all of S is (1 - 2^(-k))^(n-k) <= exp(-(n-k)/2^k). Taking a union bound over all C(n,k) sets of size k, the expected number of un-dominated sets is at most C(n,k) * exp(-(n-k)/2^k). For k = 2*log_2(n) + 1 and large n, this quantity is less than 1, proving existence. This is a classic application of the first moment method to prove that tournaments with strong domination properties exist.