Pith. sign in

REVIEW

Linear Cover Time is Exponentially Unlikely

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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 1011.3118 v1 pith:ZH7LMFFK submitted 2010-11-13 math.PR math.CO

Itai Benjamini , Ori Gurel-Gurevich , Ben Morris This is my paper · ORCID
classification math.PRmath.CO
keywords graphsimpledegreeeveryexponentiallylinearprobabilityrandom
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We show that the probability that a simple random walk covers a finite, bounded degree graph in linear time is exponentially small. More precisely, for every D and C, there exists a=a(D,C)>0 such that for any graph G, with n vertices and maximal degree D, the probability that a simple random walk, started anywhere in G, will visit every vertex of G in its first Cn steps is at most exp(-an). We conjecture that the same holds for a=a(C)>0 that does not depend on D, provided that the graph G is simple.

Discussion (0). Continue with ORCID to comment.

Pith tools