M.Sc Thesis
M.Sc Student Zuck Reut The limiting distribution of random Cayley Graphs Department of Mathematics Professor Uri Shapira

Abstract

We study the distribution of diameters of Cayley graphs of Zn/Sigma, where Sigma is a full rank sublattice of Zn, these graph are also known as multidimensional circulant graphs. In our study we consider random Cayley graphs of Zn /Sigma and we take the generating set of the graph to be of fixed size and to be chosen uniformly at random such that the resulting graph is connected. We establish a limit distribution theorem for the diameters of these random graphs. Our proof is based on connecting the diameter of the Cayley graph with the covering radius of a sublattice of Zm of covolume 1, where m is the size of the generating set of the graph. We then use an equidistribution result regarding the distribution of Hecke points, and apply this theorem to the lattices which corresponds to the Cayley graphs. This is a generalization of the work that was done by J. Marklof and A. Strömbergsson where they used the limit distribution of Frobenius numbers on m variables to study the distributions of the diameters of random Cayley graphs of Z/kZ.