TY - JOUR

T1 - Generalized Paley graphs and their complete subgraphs of orders three and four

AU - Dawsey, Madeline Locus

AU - McCarthy, Dermot

N1 - Funding Information:
The first author was supported by an AMS-Simons travel grant from the American Mathematical Society and the Simons Foundation. The second author was supported by a grant from the Simons Foundation (#353329, Dermot McCarthy).
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Nature Switzerland AG part of Springer Nature.

PY - 2021/6

Y1 - 2021/6

N2 - Let k≥ 2 be an integer. Let q be a prime power such that q≡1(modk) if q is even, or, q≡1(mod2k) if q is odd. The generalized Paley graph of order q, Gk(q) , is the graph with vertex set Fq where ab is an edge if and only if a- b is a kth power residue. We provide a formula, in terms of finite field hypergeometric functions, for the number of complete subgraphs of order four contained in Gk(q) , K4(Gk(q)) , which holds for all k. This generalizes the results of Evans, Pulham and Sheehan on the original (k= 2) Paley graph. We also provide a formula, in terms of Jacobi sums, for the number of complete subgraphs of order three contained in Gk(q) , K3(Gk(q)). In both cases, we give explicit determinations of these formulae for small k. We show that zero values of K4(Gk(q)) (resp. K3(Gk(q))) yield lower bounds for the multicolor diagonal Ramsey numbers Rk(4) = R(4 , 4 , … , 4) (resp. Rk(3)). We state explicitly these lower bounds for small k and compare to known bounds. We also examine the relationship between both K4(Gk(q)) and K3(Gk(q)) , when q is prime, and Fourier coefficients of modular forms.

AB - Let k≥ 2 be an integer. Let q be a prime power such that q≡1(modk) if q is even, or, q≡1(mod2k) if q is odd. The generalized Paley graph of order q, Gk(q) , is the graph with vertex set Fq where ab is an edge if and only if a- b is a kth power residue. We provide a formula, in terms of finite field hypergeometric functions, for the number of complete subgraphs of order four contained in Gk(q) , K4(Gk(q)) , which holds for all k. This generalizes the results of Evans, Pulham and Sheehan on the original (k= 2) Paley graph. We also provide a formula, in terms of Jacobi sums, for the number of complete subgraphs of order three contained in Gk(q) , K3(Gk(q)). In both cases, we give explicit determinations of these formulae for small k. We show that zero values of K4(Gk(q)) (resp. K3(Gk(q))) yield lower bounds for the multicolor diagonal Ramsey numbers Rk(4) = R(4 , 4 , … , 4) (resp. Rk(3)). We state explicitly these lower bounds for small k and compare to known bounds. We also examine the relationship between both K4(Gk(q)) and K3(Gk(q)) , when q is prime, and Fourier coefficients of modular forms.

UR - http://www.scopus.com/inward/record.url?scp=85102187570&partnerID=8YFLogxK

U2 - 10.1007/s40687-021-00254-7

DO - 10.1007/s40687-021-00254-7

M3 - Article

AN - SCOPUS:85102187570

SN - 2522-0144

VL - 8

JO - Research in Mathematical Sciences

JF - Research in Mathematical Sciences

IS - 2

M1 - 18

ER -