EIGENVALUE BOUNDS AND GIRTHS OF GRAPHS OF FINITE, UPPER HALF-PLANES

被引:0
作者
CELNIKER, N
机构
关键词
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For each odd prime power q = p(r) we will investigate q-2 different Cayley graphs called finite, upper half planes over F-q. We define a finite, upper half-plane by H-q = {x + y root d/x, y, epsilon F-q, y not equal 0} where F-q is the finite field with q elements and d is not a square in F-q. We define a distance k between points z and w epsilon H-q by k(z, w) = N(z-w)/(Imz) (Imw) where Nz = z $($) over bar$$ z and ($) over bar z = x-y root d and Re z = x and Imz = y. We define a graph, X(q)(d, a), by letting the elements of H-q be the vertices of the graph and defining an edge between z and w where k (z, w) = a for a fixed a epsilon F-q - {0}. We consider the origin to be the point root d. We call H-q(d, a), the finite upper half-plane depending on a fixed a and d. We first concern ourselves with whether the eigenvalues, lambda, of the adjacency matrices of the graphs satisfy the Ramanujan bound \lambda\ less than or equal to root q. Since the graphs are of degree q + 1, the paper shows a method to use the representations for the additive and multiplicative groups of each F-q to find the smaller associated isospectral matrices. We then find the eigenvalues of the isospectral matrices. A computer program has verified the Ramanujan bound for most of the graphs up to the prime power 3(5). We next concern ourselves with the girth of the graphs. This paper shows that the girths are either 3 or 4 and shows that the girth is 3 if a = 2d and q equivalent to 3(mod4) or if a and a - 3d are squares in F,. The girth is 4 if a = 2d and q equivalent to 1(mod4).
引用
收藏
页码:1 / 21
页数:21
相关论文
共 14 条
  • [1] ANGEL J, 1993, THESIS UCSD
  • [2] Bien F., 1989, NOTICES AM MATH SOC, V36, P5
  • [3] Biggs N., 1974, ALGEBRAIC GRAPH THEO
  • [4] CELNIKER N, 1990, THERE LIFE FINITE UP
  • [5] CHUNG FRK, 1980, J AM MATH SOC, V2, P187
  • [6] Diaconis Persi, 1988, GROUP REPRESENTATION, V11
  • [7] KATZ N, ESTIMATES SOTO AND 1
  • [8] LIMITATIONS ON EXPLICIT CONSTRUCTIONS OF EXPANDING GRAPHS
    KLAWE, M
    [J]. SIAM JOURNAL ON COMPUTING, 1984, 13 (01) : 156 - 166
  • [9] RAMANUJAN GRAPHS
    LUBOTZKY, A
    PHILLIPS, R
    SARNAK, P
    [J]. COMBINATORICA, 1988, 8 (03) : 261 - 277
  • [10] Mackey G. W., 1978, UNITARY GROUP REPRES