The cover times of random walks on random uniform hypergraphs

In this paper we give an expression for C(H) which is tractable for many classes of hypergraphs, and calculate C(H) and I(H) exactly for random r-regular, s-uniform hypergraphs. We find that for such hypergraphs, whp, C(H)/I(H)∼s(r−1)/r, if rs=O((loglogn)1−ϵ). For random r-regular, s-uniform multi-hypergraphs, constant r≥2, and 3≤s≤O(nϵ), we also prove that, whp, I(H)=O((n/s)logn), i.e. the inform time decreases directly with the edge size s.