Transitive Subtournaments of k-th Power Paley Digraphs and Improved Lower Bounds for Ramsey Numbers.

Let k ≥ 2 be an even integer. Let q be a prime power such that q ≡ k + 1 (mod 2 k) . We define the k-th power Paley digraph of order q, G k (q) , as the graph with vertex set F q 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 G k (q) , K 4 (G k (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 G k (q) , K 3 (G k (q)) . In both cases, we give explicit determinations of these formulae for small k. We show that zero values of K 4 (G k (q)) (resp. K 3 (G k (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 R 2 (4) and R 3 (3) . Combining with known multiplicative relations we give improved lower bounds for R t (4) , for all t ≥ 2 , and for R t (3) , for all t ≥ 3 . [ABSTRACT FROM AUTHOR]