Transitive subtournaments of $k$-th power Paley digraphs and improved lower bounds for Ramsey numbers

Abstract

Let $k\ge 2$ be an even integer. Let $q$ be a prime power such that $q\equiv k+1(\mathrm{mod}2k)$. We define the $\text{k-th power Paley digraph}$ of order $q$, $G_k(q)$, as the graph with vertex set ${\mathbb{F}}_q$ where $a\to 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)$, ${\mathcal{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)$, ${\mathcal{K}}_3(G_k(q))$. In both cases, we give explicit determinations of these formulae for small $k$. We show that zero values of ${\mathcal{K}}_4(G_k(q))$ (resp. ${\mathcal{K}}_3(G_k(q))$) yield lower bounds for the multicolor directed Ramsey numbers $R_{\frac{k}{2}}(4)=R(4,4,\cdots ,4)$ (resp. $R_{\frac{k}{2}}(3)$). We state explicitly these lower bounds for $k\le 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\ge 2$, and for $R_t(3)$, for all $t\ge 3$.

arXiv admin note: text overlap with arXiv:2006.14716