Combinatorics: David Ellis (Queen Mary) "Random graphs with constant r-balls"

Mon, 09/04/201811:00-12:30
IIAS, room 130, Feldman Building, Givat Ram

Let F be an infinite, vertex-transitive graph. We say that a finite graph G is {\em r-locally F} if every ball of radius r in G is isomorphic to the ball of radius r in F. We investigate the properties of finite graphs that are r-locally F, for various choices of r and F. When F is the infinite (2d)-regular tree, such graphs are precisely the (2d)-regular graphs with high girth, which have been extensively studied. We consider the case where F is the d-dimensional square lattice, L^d. It turns out that for r > 2, graphs which are r-locally L^d have a highly rigid, global, 'algebraic' structure - much more rigid than that of regular graphs with high girth. Similar 'local-to-global rigidity' phenomena occur for all Cayley graphs of torsion-free groups with polynomial growth, by recent results of de la Salle and Tessera. It is also natural to ask about the properties of a {\em random} n-vertex graph that is r-locally F, for various choices of r and F. We prove that if r > \max\{2,d/2}, then a random unlabelled n-vertex graph that is r-locally L^d, has largest component of size o(n), with high probability. This is in stark contrast to a random (2d)-regular graph of high girth, which is connected with high probability for all d > 1. Our proofs employ techniques and results from combinatorics, topology, group theory and analytic number theory. Of course, many open questions remain! Joint work with Itai Benjamini (WIS).