Differential equations for random processes and random graphs

DOI10.1214/aoap/1177004612zbMath0847.05084WikidataQ56621902 ScholiaQ56621902MaRDI QIDQ1916491

Nicholas C. Wormald

Publication date: 8 July 1996

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1177004612

zbMATH Keywords

differential equations; random processes; random graph; independent sets; random regular graph; \(d\)-process

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

Related Items

Connectedness of graphs generated by a random d-process, Digital morphogenesis via Schelling segregation, An identity derived from the solution of a class of differential equations for the evolution of a key agreement protocol, Closing Gaps in Asymptotic Fair Division, Greedy Matching in Bipartite Random Graphs, A Dynamic Contagion Risk Model with Recovery Features, The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘), Large Deviation Principle for the Greedy Exploration Algorithm over Erd\"os-R\'enyi Graphs, Almost all trees are almost graceful, Diffusion in Random Networks: Impact of Degree Distribution, Constructing concrete hard instances of the maximum independent set problem, Greedy Bipartite Matching in Random Type Poisson Arrival Model, The spread of fire on a random multigraph, On the Chromatic Index of Random Uniform Hypergraphs, Minimum Power Dominating Sets of Random Cubic Graphs, Orientability Thresholds for Random Hypergraphs, Convergence of Achlioptas Processes via Differential Equations with Unique Solutions, When does the K₄‐free process stop?, The C_ℓ‐free process, A scaling limit for the degree distribution in sublinear preferential attachment schemes, On conceptually simple algorithms for variants of online bipartite matching, Rigorous results for random (\(2+p)\)-SAT, Lower bounds for random 3-SAT via differential equations, Almost all graphs with average degree 4 are 3-colorable, FINANCIAL CONTAGION IN A STOCHASTIC BLOCK MODEL, On the modularity of 3‐regular random graphs and random graphs with given degree sequences, Biased random k‐SAT, The number of \(n\)-queens configurations, Contagion risks and security investment in directed networks, Properties of regular graphs with large girth via local algorithms, Unperturbed Schelling segregation in two or three dimensions, A simple population protocol for fast robust approximate majority, Dense subgraphs in the \(H\)-free process, Cores of random \(r\)-partite hypergraphs, The cook-book approach to the differential equation method, Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances, Bootstrap percolation in living neural networks, On the thresholds in linear and nonlinear Boolean equations, Scaling limits for continuous opinion dynamics systems, Cleaning random \(d\)-regular graphs with brooms, On a general many-dimensional excited random walk, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, An integrated model for fire sales and default contagion, \(k\)-core architecture and \(k\)-core percolation on complex networks, Regular random \(k\)-SAT: Properties of balanced formulas, Edge percolation on a random regular graph of low degree, A central limit theorem via differential equations, Connected domination of regular graphs, Large independent sets in random regular graphs, Density-profile processes describing biological signaling networks: Almost sure convergence to deterministic trajectories, On a random graph evolving by degrees, Small maximal matchings in random graphs., Analysis of greedy algorithms on graphs with bounded degrees, Hamiltonian decompositions of random bipartite regular graphs., The 3-XORSAT threshold., On the instability of matching queues, Critical random graphs and the differential equations technique, Structure of large random hypergraphs, The design of novel distributed protocols from differential equations, A sharp threshold for bootstrap percolation in a random hypergraph, Typicality and entropy of processes on infinite trees, The matching process and independent process in random regular graphs and hypergraphs, Epidemic spreading and equilibrium social distancing in heterogeneous networks, Depth first exploration of a configuration model, On the power of random greedy algorithms, GHS algorithm on a graph with random weights, Universality for critical heavy-tailed network models: metric structure of maximal components, Heavy-tailed configuration models at criticality, Preferential attachment without vertex growth: emergence of the giant component, Super solutions of random \((3 + p)\)-SAT, The jamming constant of uniform random graphs, Modelling population processes with random initial conditions, Bounds on the bisection width for random \(d\)-regular graphs, Large independent sets in regular graphs of large girth, Phase transition in a random NK landscape model, Maximum independent sets on random regular graphs, Typical case complexity of satisfiability algorithms and the threshold phenomenon, An algorithm for random signed 3-SAT with intervals, Phase transitions of PP-complete satisfiability problems, A gentle introduction to the differential equation method and dynamic concentration, RESILIENCE TO CONTAGION IN FINANCIAL NETWORKS, The Bohman-Frieze process near criticality, On the normality of giant components, Complex Contagions on Configuration Model Graphs with a Power-Law Degree Distribution, Locally Dense Independent Sets in Regular Graphs of Large Girth—An Example of a New Approach, Ramsey games with giants, Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs, The evolution of subcritical Achlioptas processes, Construction of Directed Assortative Configuration Graphs, Selecting Complementary Pairs of Literals, Induced Forests in Regular Graphs with Large Girth, Giant Component in Random Multipartite Graphs with Given Degree Sequences, Small maximal matchings of random cubic graphs