##### Department of Mathematics,

University of California San Diego

****************************

### Colloquium

## Laszlo Lovasz

#### Microsoft Research

## Discrete Analytic Functions and Global Information from Local Observation

##### Abstract:

We observe a certain random process on a graph "locally", i.e., in theneighborhood of a node, and would like to derive information about"global" properties of the graph. For example, what can we know about agraph based on observing the returns of a random walk to a given node?This can be considered as a discrete version of "Can you hear the shapeof a drum?"Our main result concerns a graph embedded in an orientable surface withgenus g, and a process, consisting of random excitations of edges andrandom balancing around nodes and faces. It is shown that by observingthe process locally in a "small" neighborhood of any node sufficiently(but only polynomially) long, we can determine the genus of the surface.The result depends on the notion of "discrete analytic functions" ongraphs embedded in a surface, and extensions of basic results onanalytic functions to such discrete objects; one of these is the factthat such functions are determined by their values in a "small"neighborhood of any node.This is joint work with Itai Benjamini.

Host: Van Vu

### April 1, 2003

### 3:00 PM

### AP&M 6438

****************************