OFFSET
0,2
COMMENTS
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.
A Paley graph is constructed from the members of a finite field F by connecting pairs of elements that differ by a quadratic residue.
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.
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)=1163 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.
All known smallest sizes of an n-paradoxical tournament are primes congruent to 3 mod 4.
No reasonable values of a(n) for n > 6 are known.
Lower and upper bounds are given in the papers given in the references section.
LINKS
P. Erdős, On a Problem in Graph Theory, The Mathematical Gazette, 47.361 (1963), 220-223.
R. L. Graham and J. H. S. Spencer, A Constructive Solution to a Tournament Problem, Canadian Mathematical Bulletin 14.1, (1971), 45-48.
K. B. Reid and A. A. McRae and S.M. Hedetniemi and S. T. Hedetniemi, Domination and irredundance in tournaments, Australas. J Comb., 29 (2004), 157-172.
E. Szekeres and G. Szekeres, On a Problem of Schütte and Erdős, The Mathematical Gazette 49.369 (1965), 290-293.
EXAMPLE
For n=1, a(1)=3 vertices, each one being the predecessor of exactly one of the other two.
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.
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.
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Julien Rouyer, Jun 12 2023
EXTENSIONS
a(6) corrected by Nicholas Stefan Georgescu, Jul 03 2024
STATUS
approved