|
%I #18 Jul 21 2023 20:40:57
%S 1,3,7,19,67,331,1263
%N Smallest size of an n-paradoxical tournament built as a directed Paley graph.
%C An n-paradoxical tournament consists of a complete oriented 1-graph (each pair of vertices are connected by exactly one directed edge) in which all possible groups of n vertices have a common predecessor.
%C A Paley graph is constructed from the members of a finite field F by connecting pairs of elements that differ by a quadratic residue.
%C In an n-paradoxical tournament built as a directed Paley graph, a vertex x is the predecessor of a vertex y if and only if y-x is a quadratic residue of F.
%C a(0)=1, a(1)=3, a(2)=7 and a(3)=19 are proved to be the smallest sizes of an n-paradoxical tournament. The following a(4)=67, a(5)=331 and a(6)=1263 are only the smallest sizes of the known solutions for an n-paradoxical tournament but they are the smallest sizes of an n-paradoxical tournament built as a directed Paley graph.
%C All known smallest sizes of an n-paradoxical tournament are primes congruent to 3 mod 4.
%C No reasonable values of a(n) for n > 6 are known.
%C Lower and upper bounds are given in the papers given in the references section.
%H P. Erdős, <a href="https://www.jstor.org/stable/3613396">On a Problem in Graph Theory</a>, The Mathematical Gazette, 47.361 (1963), 220-223.
%H R. L. Graham and J. H. S. Spencer, <a href="https://www.cambridge.org/core/journals/canadian-mathematical-bulletin/article/constructive-solution-to-a-tournament-problem/F6DDB2DE033EE8AD7B5E9BE0EBEDE0D6">A Constructive Solution to a Tournament Problem</a>, Canadian Mathematical Bulletin 14.1, (1971), 45-48.
%H K. B. Reid and A. A. McRae and S.M. Hedetniemi and S. T. Hedetniemi, <a href="https://ajc.maths.uq.edu.au/pdf/29/ajc_v29_p157.pdf">Domination and irredundance in tournaments</a>, Australas. J Comb., 29 (2004), 157-172.
%H E. Szekeres and G. Szekeres, <a href="https://www.jstor.org/stable/3612854">On a Problem of Schütte and Erdős</a>, The Mathematical Gazette 49.369 (1965), 290-293.
%e For n=1, a(1)=3 vertices, each one being the predecessor of exactly one of the other two.
%e For n=2, a(2)=7 vertices named 0,1,2,3,4,5,6, each vertex x being the predecessor of vertices x+1, x+2, x+4 mod 7.
%e For n=3, a(3)=19 vertices named 0,1,2,...,18, each vertex x being the predecessor of vertices x+1, x+4, x+5, x+6, x+7, x+9, x+11, x+16, x+17 mod 19.
%K nonn,hard,more
%O 0,2
%A _Julien Rouyer_, Jun 12 2023
|
