2023/11/03 by Dermot McCarthy, McCarthy, Dermot, Mason Springfield +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.2311.02135
openalex publication_date 2023/11/03 · openalex created_date 2023/11/08 · openalex updated_date 2026/07/28
Let k ≥ 2 be an even integer. Let q be a prime power such that q ≡ k+1 \pmod 2k. We define the k-th power Paley digraph of order q, Gk(q), as the graph with vertex set \mathbbFq where a → b is an edge if and only if b-a is a k-th power residue. This generalizes the (k=2) Paley Tournament. We provide a formula, in terms of finite field hypergeometric functions, for the number of transitive subtournaments of order four contained in Gk(q), K4(Gk(q)), which holds for all k. We also provide a formula, in terms of Jacobi sums, for the number of transitive subtournaments 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 directed Ramsey numbers R(k)/(2)(4)=R(4,4,⋯,4) (resp. R(k)/(2)(3)). We state explicitly these lower bounds for k≤ 10 and compare to known bounds, showing improvement for R2(4) and R3(3). Combining with known multiplicative relations we give improved lower bounds for Rt(4), for all t≥ 2, and for Rt(3), for all t ≥ 3.