The critical random graph, with martingales

DOI10.1007/S11856-010-0019-8zbMath1215.05168arXivmath/0512201OpenAlexW2160478770MaRDI QIDQ980493

Yuval Peres, Asaf Nachmias

Publication date: 29 June 2010

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0512201

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items (24)

The critical window in random digraphs ⋮ Unusually large components in near-critical Erdős–Rényi graphs via ballot theorems ⋮ An elementary approach to component sizes in critical random graphs ⋮ The scaling window for a random graph with a given degree sequence ⋮ The largest component in critical random intersection graphs ⋮ Critical percolation on scale-free random graphs: new universality class for the configuration model ⋮ Universality for critical heavy-tailed network models: metric structure of maximal components ⋮ Large deviations of the greedy independent set algorithm on sparse random graphs ⋮ Enumerative combinatorics. Abstracts from the workshop held December 11--17, 2022 ⋮ The probability of unusually large components for critical percolation on random \(d\)-regular graphs ⋮ The continuum limit of critical random graphs ⋮ Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome? ⋮ Average update times for fully-dynamic all-pairs shortest paths ⋮ Unnamed Item ⋮ Swendsen‐Wang algorithm on the mean‐field Potts model ⋮ Critical random graphs: Diameter and mixing time ⋮ Critical percolation on random regular graphs ⋮ Critical epidemics, random graphs, and Brownian motion with a parabolic drift ⋮ Largest Components in Random Hypergraphs ⋮ A power law of order 1/4 for critical mean-field Swendsen-Wang dynamics ⋮ Size of the largest component in a critical graph ⋮ The probability of unusually large components in the near-critical Erdős–Rényi graph ⋮ The Phase Transition in Multitype Binomial Random Graphs ⋮ Critical percolation on random regular graphs

Cites Work

• Brownian excursions, critical random graphs and the multiplicative coalescent
• On the largest component of the random graph at a nearcritical stage
• Critical percolation on random regular graphs
• The transitive closure of a random digraph
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• The Evolution of Random Graphs
• Symmetric sampling procedures, general epidemic processes and their threshold limit theorems
• Component behavior near the critical point of the random graph process
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• Probability with Martingales
• The Structure of a Random Graph at the Point of the Phase Transition
• The birth of the giant component
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Probability

This page was built for publication: The critical random graph, with martingales