Pith. sign in

REVIEW 1 cited by

Critical random graphs: Diameter and mixing time

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv math/0701316 v4 pith:JW3GKHXH submitted 2007-01-11 math.PR math.CO

classification math.PRmath.CO
keywords mathcalrandomclusterscriticaldiametergraphmixingorder
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Let $\mathcal{C}_1$ denote the largest connected component of the critical Erd\H{o}s--R\'{e}nyi random graph $G(n,{\frac{1}{n}})$. We show that, typically, the diameter of $\mathcal{C}_1$ is of order $n^{1/3}$ and the mixing time of the lazy simple random walk on $\mathcal{C}_1$ is of order $n$. The latter answers a question of Benjamini, Kozma and Wormald. These results extend to clusters of size $n^{2/3}$ of $p$-bond percolation on any $d$-regular $n$-vertex graph where such clusters exist, provided that $p(d-1)\le1+O(n^{-1/3})$.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Meeting and coalescence times for random walks in the largest component of the Erd\H{o}s-R\'enyi random graph

    math.PR 2026-07 accept novelty 8.0 of 10

    Expected meeting, coalescence, and voter-consensus times on the Erdős–Rényi giant are Θ(n) throughout the fixed-supercritical, slightly-supercritical, and critical regimes.

Pith tools