Hitting times, commute times, and cover times for random walks on random hypergraphs

DOI10.1016/J.SPL.2019.06.011MaRDI QIDQ2273705zbMATH OpenOpenAlexFDO

Authors Amine Helali, M. Löwe

Publication date 25 September 2019

Published in Statistics \& Probability Letters (Search for Journal in Brave)

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

zbMATH Keywords

hitting timerandom walkscover timerandom hypergraphscommute time

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Random walks on graphs (05C81)

Abstract: We consider random walk on the structure given by a random hypergraph in the regime where there is a unique giant component. We give the asymptotics for hitting times, cover times, and commute times and show that the results obtained for random walk on random graphs are universal.

Recommendations

• The cover times of random walks on random uniform hypergraphs
• Expected hitting and cover times of random walks on some special graphs
• On the Cover Time for Random Walks on Random Graphs
• Hitting times for random walks on vertex-transitive graphs
• On the cover time of random walks on graphs
• scientific article; zbMATH DE number 109323
• On hitting times for a simple random walk on dense Erdös-Rényi random graphs

Cites work

• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• A phase transition for the limiting spectral density of random matrices
• Asymptotic normality of the size of the giant component in a random hypergraph
• Exploring hypergraphs with martingales
• First-passage properties of the Erdos–Renyi random graph
• Loose Laplacian spectra of random hypergraphs
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On hitting times for a simple random walk on dense Erdös-Rényi random graphs
• Random graphs and complex networks. Volume 1
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• The cover times of random walks on random uniform hypergraphs
• The semicircle law for matrices with ergodic entries

Cited in

(13)

• The cover times of random walks on random uniform hypergraphs
• The hitting time of random walk on unicyclic graphs
• Hitting and commute times in large random neighborhood graphs
• Return probabilities and hitting times of random walks on sparse Erdös-Rényi graphs
• Concentration of hitting times in Erdős-Rényi graphs
• Decomposing hitting times of walks on graphs into simpler ones
• Spectra of random regular hypergraphs
• Expected hitting and cover times of random walks on some special graphs
• Cover and hitting times of hyperbolic random graphs
• Hitting times for random walks on vertex-transitive graphs
• Hitting time of large subsets of the hypercube
• Hitting times for random walks on subdivision and triangulation graphs
• A central limit theorem for the mean starting hitting time for a random walk on a random graph

This page was built for publication: Hitting times, commute times, and cover times for random walks on random hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2273705)