Determining the Genus of a Map by Local Observation of a Simple Random Process

arXivmath/0202127MaRDI QIDQ6471637

Publication date: 13 February 2002

Abstract: Given a graph embedded in an orientable surface, a process consisting of random excitations and random node and face balancing is constructed and analyzed. It is shown that given a priori bounds g' on the genus and n' on the number of nodes, one can determine the genus of the surface from local observations of the process restricted to any connected subgraph which cannot be separated from the rest of the graph by fewer than 16g' nodes. The observation time and the computation time are polynomial in n'^g'. The process constructs slightly perturbed random ``discrete analytic functions on the surface, and the key fact in the analysis is that such a function cannot vanish on a large piece of the surface.

This page was built for publication: Determining the Genus of a Map by Local Observation of a Simple Random Process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6471637)