{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-11","reactions":{}}