Date
Tue, 14 Oct 2014
Time
14:30 - 15:30
Location
L6
Speaker
David Ellis
Organisation
Queen Mary University of London

We study the properties of finite graphs in which the ball of radius $r$ around each vertex induces a graph isomorphic to some fixed graph $F$. (Such a graph is said to be $r$-locally-$F$.) This is a natural extension of the study of regular graphs, and of the study of graphs of constant link. We focus on the case where $F$ is $\mathbb{L}^d$, the $d$-dimensional integer lattice. We obtain a characterisation of all the finite graphs in which the ball of radius $3$ around each vertex is isomorphic to the ball of radius $3$ in $\mathbb{L}^d$, for each integer $d$. These graphs have a very rigidly proscribed global structure, much more so than that of $(2d)$-regular graphs. (They can be viewed as quotient lattices in certain 'flat orbifolds'.) Our results are best possible in the sense that '3' cannot be replaced with '2'. Our proofs use a mixture of techniques and results from combinatorics, algebraic topology and group theory. We will also discuss some results and open problems on the properties of a random n-vertex graph which is $r$-locally-$F$. This is all joint work with Itai Benjamini (Weizmann Institute of Science). 

Please contact us with feedback and comments about this page. Last updated on 04 Apr 2022 14:57.