14.3 Probabilistic method in graph theory

The probabilistic method is a powerful tool in graph theory, using probability to prove the existence of graphs with specific properties. It simplifies complex proofs and provides results for graphs that are difficult to construct explicitly.

Key techniques include the first moment method, second moment method, and Lovász Local Lemma. These approaches analyze expected values, variances, and dependencies to demonstrate the existence of graphs with desired characteristics like large girth, specific colorings, or avoiding certain subgraphs.

Fundamentals of the Probabilistic Method

Principles of probabilistic method

• Core concept uses probability to prove graph property existence without explicit construction
• Key steps define probability space of graphs and show desired properties occur with positive probability
• Advantages simplify proofs for complex properties and provide existence results for hard-to-construct graphs
• Common distributions include uniform distribution on graphs and Erdős-Rényi random graph model (G(n,p))

Specific Techniques and Applications

First moment method applications

• Based on linearity of expectation E[X] = E[X₁] + E[X₂] + ... + E[Xₙ]
• Steps define random variable X, calculate E[X], use E[X] to prove existence
• Proves existence of graphs with large girth and chromatic number (Erdős' construction)
• Demonstrates graphs with specific edge density properties (Turán's theorem)

Second moment method analysis

• Uses expectation and variance Var(X) = E[X²] - (E[X])²
• Key components Chebyshev's inequality bounds probability of deviation from mean
• Steps define X, calculate E[X] and Var(X), apply $P(|X - E[X]| \geq t) \leq \frac{Var(X)}{t^2}$
• Analyzes threshold functions in random graphs (connectivity, Hamilton cycles)
• Proves concentration of graph parameters around means (chromatic number, independence number)

Lovász Local Lemma for graphs

• Proves existence of objects satisfying multiple constraints in dependency graph
• Key components include dependency graph and probability bounds for individual events
• General form if events have limited dependence and small individual probabilities, avoiding all events has positive probability
• Proves existence of graphs with specific colorings (acyclic edge coloring)
• Demonstrates graphs avoiding certain subgraphs (Ramsey-type results)
• Variants include symmetric version and algorithmic versions for finding desired structures