Local-Global Phenomena in Graphs

Summary

This is a survey of a number of recent papers dealing with graphs from a geometric perspective. The main theme of these studies is the relationship between graph properties that are local in nature, and global graph parameters. Connections with the theory of distributed computing are pointed out and many open problems are presented.

Introduction

How well can global properties of a graph be inferred from observations that are purely local? This general question gives rise to numerous interesting problems that we want to discuss here. Such a local-global approach is often taken in geometry, where it has a long and successful history, but a systematic study of graphs from this perspective has not begun until recently. Nevertheless, a number of older results in graph theory do fit very nicely into this framework, as we later point out. Most of the specific problems fall in two categories. In the first, local structural information on the graph is collected and then used to derive certain consequences for the graph as a whole. The other class of problems concerns consistency of local data. Namely, one asks to characterize those sets of local data that may come from some graphs.

As the reader will soon see, the local-global paradigm leads to many questions in which graphs are viewed as geometric objects, a point of view that we believe can greatly benefit graph theory. Besides the geometric connection, ties also exist with the theory of combinatorial algorithms.