Hitting time of connectedness in the random hypercube process

2024/04/14 by Sahar Diskin, Michael Krivelevich, Diskin, Sahar +1
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2404.09289

openalex publication_date 2024/04/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a short and self-contained proof of a classical result due to Bollobás (1990): in the random hypercube process, with high probability the hitting time of connectedness equals the hitting time of having minimum degree at least one.

Related

• Hitting time of large subsets of the hypercube
• On the strength of connectedness of a random hypergraph
• A note on random walks in a hypercube
• Threshold and hitting time for high-order connectivity in random hypergraphs
• Stopping Times of Random Walks on a Hypercube