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

Madeline Locus Dawsey, Dermot McCarthy

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Article number18
JournalResearch in Mathematical Sciences
Volume8
Issue number2
DOIs
StatePublished - Jun 2021

Fingerprint Dive into the research topics of 'Generalized Paley graphs and their complete subgraphs of orders three and four'. Together they form a unique fingerprint.

Cite this