Waiting for a bat to fly by (in polynomial time)

Simple item page
dc.creatorBenjamini, Itai
dc.creatorKozma, Gady
dc.creatorLovasz, Laszlo
dc.creatorRomik, Dan
dc.creatorTardos, Gabor
dc.date2003-10-28
dc.date.accessioned2026-07-07T05:02:18Z
dc.date.available2026-07-07T05:02:18Z
dc.descriptionWe observe returns of a simple random walk on a finite graph to a fixed node, and would like to infer properties of the graph, in particular properties of the spectrum of the transition matrix. This is not possible in general, but at least the eigenvalues can be recovered under fairly general conditions, e.g. when the graph has a node-transitive automorphism group. The main result is that by observing polynomially many returns, it is possible to estimate the spectral gap of such a graph up to a constant factor.
dc.identifierhttps://arxiv.org/abs/math/0310435
dc.identifierhttp://arxiv.org/abs/math/0310435
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/69001
dc.subjectProbability
dc.subjectCombinatorics
dc.titleWaiting for a bat to fly by (in polynomial time)
dc.typetext

Files

Collections

arXiv