On Wormald's differential equation method

2019/05/22 by Lutz Warnke, Warnke, Lutz · 3 citations
Computer Science · Mathematics · #60C05 #60J10 #68Q87 #68W20 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1905.08928

openalex publication_date 2019/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Boosted second moment method in random regular graphs
• Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization
• Online matching on stochastic block model

Related

• Extending Wormald's Differential Equation Method to One-sided Bounds
• Ordinary Differential Equation Models and their Computation Methods
• A gentle introduction to the differential equation method and dynamic concentration
• Long-time dynamics of stochastic differential equations
• An Algorithmic Introduction to Numerical Simulation of Stochastic Differential Equations