Russell, George Edward
(1995)
Spectral properties of graphs derived from groups.
PhD thesis, London School of Economics and Political Science.
Abstract
This thesis is primarily about spectral measures and walkgenerating functions of lattices. Formally a lattice is obtained from a finitelygenerated abelian group G, a finite set Y, and a finite subset L of Gxx. Informally a lattice is likely to be some structure in ndimensional space such as a hexagonal or cubic lattice. Spectral measures and walkgenerating functions determine each other, and are relevant to Markov Chains and networks of resistances. Formulae for spectral measures and walk generating functions of lattices are found, and generalised to sumdifference graphs and graphs obtained from groups with large abelian subgroups. Formulae are also found for walk generating functions for modified lattices. Lattices may be modified by a finite set of changes to edges or vertices, but also by an infinite but periodic set of modifications (such as a row of points being removed). For example, this makes it possible to find exact formulae for Markov Chains where two interacting particles move around a lattice. However only one infinite periodic set of modifications can be so handled; we show that with directed lattices with two infinite periodic sets of modifications, even finding if two points are connected can be equivalent to the Halting Problem. New methods are found for discovering what a spectral measure looks like. We develop techniques in the theory of complex functions of several variables to provide criteria which make it possible to show that a spectral measure is wellbehaved at some point (in the sense that its density function is analytic) if local properties of certain analytic functions are satisfied globally.
Actions (login required)

Record administration  authorised staff only 