Id: arxiv/2602.10970 Url: https://arxiv.org/abs/2602.10970 Tags: math.CO, math.PR Score: 0 Title: Note on the trace of random walks on pseudorandom graphs Domain: math.CO Source: arxiv Authors: Yaobin Chen, Yiting Wang Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-11 Page: https://delphi.science/r/arxiv/2602.10970 We study the graph-theoretic properties of the trace of random walks on pseudorandom graphs. We show that for any $\varepsilon>0$, there exists a constant $C$ such that the cover time of an $(n,d,λ)$-graph $G$ with $d/λ\ge C$ is at most $(1+\varepsilon)n\log n$, meaning the expected number of steps needed to reach all vertices at least once is at most $(1+\varepsilon)n\log n$ regardless of the starting vertex. Furthermore, we prove that with high probability, the trace of a random walk of length $(1+\varepsilon)n\log n$ on $G$ is Hamiltonian, regardless of the starting vertex. These results…