Probabilistic Combinatorics

What if one could prove that something exists without ever building it? Erdős discovered this in 1947 and opened an entire field. The probabilistic method today underpins the analysis of randomized algorithms, hash functions, and network design.

• **Hash function analysis:** first moment bounds on collision probabilities determine table size requirements
• **Random SAT algorithms:** walkSAT and DPLL are analyzed through concentration of random variables
• **Network algorithms:** load balancing guarantees follow from probabilistic arguments about how load distributes

Предварительные знания

• Ramsey Theory: Order from Chaos

The Probabilistic Method

Erdős's probabilistic method is a powerful tool for proving the existence of combinatorial objects without constructing them. The core idea: if a random object has a desired property with positive probability, that object exists.

**The basic principle:** let X be a random variable over probability space Ω. If E[X] > 0, then P(X > 0) > 0, so some ω ∈ Ω has X(ω) > 0. Dually: if E[X] < |Ω|, some ω has X(ω) < |Ω|.

The First Moment Method and Chromatic Number

The first moment method uses Markov's inequality P(X ≥ a) ≤ E[X]/a to give upper bounds on probabilities of large values. Applied to random graphs G(n,p), it yields upper bounds on the chromatic number χ(G).

**Greedy coloring** gives χ(G) ≤ Δ+1 where Δ is the maximum degree. For G(n,p), the expected degree is E[deg(v)] = (n-1)p ≈ np. Concentration of degrees around np then gives the upper bound on χ.

The Second Moment Method

The second moment method (Paley-Zygmund inequality) proves P(X > 0) ≥ (E[X])² / E[X²]. When Var[X]/E[X]² → 0, the random variable X concentrates tightly around its mean, X ≈ E[X] with probability approaching 1.

**Practical impact:** the second moment method is used to analyze random SAT instances, hash functions, and data structures. When variance is small relative to E[X]², the structure is 'typical' and predictable, which is exactly what makes randomized algorithms analyzable.

The Alteration Method

The alteration method refines the basic probabilistic argument: build a random structure, then 'fix' the bad parts. For independent sets: include each vertex with probability p, then delete one vertex from each edge. What remains is independent with expected size ≥ np - m·p².

**Inclusion-exclusion** computes |A₁ ∪ ... ∪ Aₙ| via sums of intersections: |⋃Aᵢ| = Σ|Aᵢ| - Σ|Aᵢ∩Aⱼ| + ... The probabilistic version, Möbius inversion, generalizes this to partially ordered sets.

Key Ideas

• **Basic principle:** E[X] > 0 ⟹ P(X > 0) > 0 ⟹ some outcome has X > 0
• **First moment method:** P(X ≥ a) ≤ E[X]/a via Markov, upper bounds on probabilities of rare events
• **Second moment method:** Var[X]/E[X]² → 0 ⟹ X concentrates around E[X]
• **Alteration:** build random, fix bad parts, the resulting lower bound on α(G) beats naive greedy

Connected Topics

Probabilistic combinatorics runs through all the advanced topics in this course:

• Random Graphs — All threshold results for G(n,p) are proved using first/second moment methods and the alteration technique
• Ramsey Theory — The lower bound R(r,r) > 2^(r/2) was the first and most important application of the probabilistic method

Вопросы для размышления

• What is the fundamental difference between a probabilistic existence proof and a constructive one?
• Why is the second moment method strictly stronger than the first moment method for proving P(X > 0) → 1?
• How can one apply the alteration method to find a large independent set in a concrete graph?

Связанные уроки

• prob-02-combinatorics