Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Isoperimetric Numbers of Regular Graphs of High Degree with Applications to Arithmetic Riemann Surfaces. | Isoperimetric Numbers of Regular Graphs of High Degree with Applications to Arithmetic Riemann Surfaces Dominic Lanphier Department of Mathematics Western Kentucky University Bowling Green KY 42101 . Jason Rosenhouse Department of Mathematics and Statistics James Madison University Harrisonburg VA 22807 . rosenhjd@ Submitted Feb 7 2011 Accepted Jul 21 2011 Published Aug 12 2011 Mathematics Subject Classifications 05C40 30F10 Abstract We derive upper and lower bounds on the isoperimetric numbers and bisection widths of a large class of regular graphs of high degree. Our methods are combinatorial and do not require a knowledge of the eigenvalue spectrum. We apply these bounds to random regular graphs of high degree and the Platonic graphs over the rings Zn. In the latter case we show that these graphs are generally nonRamanujan for composite n and we also give sharp asymptotic bounds for the isoperimetric numbers. We conclude by giving bounds on the Cheeger constants of arithmetic Riemann surfaces. For a large class of these surfaces these bounds are an improvement over the known asymptotic bounds. 1 Introduction Let G be a graph and let A c V G . The boundary of A denoted by dA is the set of edges of G having precisely one endpoint in A. The isoperimetric number of G is tof A A where the infimum is taken over all subsets A c V G satisfying A 1 V G . The isoperimetric number of a graph was introduced by Buser in 4 as a discrete analog of The author is partially supported by grant 223120 of Western Kentucky University THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P164 1 the Cheeger constant used to study the eigenvalue spectrum of a Riemannian manifold. The bisection width bw G is infA ỠA where n 2 A 1. For a regular graph of degree k it is now standard to estimate h G in terms of the second largest eigenvalue of the adjacency matrix of G as in 7 16 and 17 . This approach is especially suited to Cayley graphs and quotients .
