A362137 Smallest size of an n-paradoxical tournament built as a directed Paley graph.

1, 3, 7, 19, 67, 331, 1163

Offset: 0

Author

Julien Rouyer, Jun 12 2023

Keywords

• nonn
• hard
• more

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.

Examples

			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.
		

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.

Extensions

a(6) corrected by Nicholas Stefan Georgescu, Jul 03 2024