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

期刊论文
发表日期：

2024年5月21日

查看全文

Dermot McCarthy,
Mason Springfield

摘要

Let $k \ge 2$ $k \geq 2$ be an even integer. Let q be a prime power such that $q \equiv k+1 (\text {mod}\,\,2k)$ $q \equiv k + 1 (mod 2 k)$ . We define the k-th power Paley digraph of order q, $G_k(q)$ $G_{k} (q)$ , as the graph with vertex set $\mathbb {F}_q$ $F_{q}$ where $a \rightarrow b$ $a \to b$ is an edge if and only if $b-a$ $b - a$ is a k-th power residue. This generalizes the ( $k=2$ $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)$ $G_{k} (q)$ , $\mathcal {K}_4(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)$ $G_{k} (q)$ , $\mathcal {K}_3(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 $\mathcal {K}_4(G_k(q))$ $K_{4} (G_{k} (q))$ (resp. $\mathcal {K}_3(G_k(q))$ $K_{3} (G_{k} (q))$ ) yield lower bounds for the multicolor directed Ramsey numbers $R_{\frac{k}{2}}(4)=R(4,4,\ldots ,4)$ $R_{\frac{k}{2}} (4) = R (4, 4, \dots, 4)$ (resp. $R_{\frac{k}{2}}(3)$ $R_{\frac{k}{2}} (3)$ ). We state explicitly these lower bounds for $k\le 10$ $k \leq 10$ and compare to known bounds, showing improvement for $R_2(4)$ $R_{2} (4)$ and $R_3(3)$ $R_{3} (3)$ . Combining with known multiplicative relations we give improved lower bounds for $R_{t}(4)$ $R_{t} (4)$ , for all $t\ge 2$ $t \geq 2$ , and for $R_{t}(3)$ $R_{t} (3)$ , for all $t \ge 3$ $t \geq 3$ .