On Wormald's differential equation method

Abstract

This note contains a short and simple proof of Wormald's differential equation method (that yields slightly improved approximation guarantees and error probabilities). This powerful method uses differential equations to approximate the time-evolution/dynamics of random processes and algorithms.

7 pages; minor corrections

References in corpus (1)

• The phase transition in bounded-size Achlioptas processes

Cited by in corpus (6)

• Prague dimension of random graphs
• Preferential attachment without vertex growth: emergence of the giant component
• On the modularity of 3-regular random graphs and random graphs with given degree sequences
• On the power of random greedy algorithms
• Convergence of Coupon Collecting Process via Wormald's Differential Equation Method
• On partial Steiner $(n,r,\ell )$-system process