A122026 Least number m such that every tournament with at least m nodes contains the acyclic n-node tournament.

0, 1, 2, 4, 8, 14, 28

Offset

0,3

Comments

A Ramsey-like number but defined for tournaments (i.e., directed graphs in which each node-pair is joined by exactly one arc) rather than undirected graphs.

It is not hard to show that a(n) always exists and a(n) is nondecreasing.

The lower bounds a(4)>=8 and a(5)>=14 and a(6)>=28 arise from the cyclic tournaments with offsets 1,2,4 mod 7; the same is true of offsets 1,3,9,2,6,5 mod 13 and the "QRgraph" in GF(3^3) with 27 vertices.

The following lower bounds a(n)>=P+1 arise from QRgraph(P) where P is prime and P=3 (mod 4): a(8)>=48, a(9)>=84, a(10)>=108, a(12)>=200, a(13)>=272.

This is almost certainly different from the other sequences currently in the OEIS which begin 1,2,4,8,14,28.

References

K. B. Reid, Tournaments, in Handbook of Graph Theory; see p. 167.

Links

Table of n, a(n) for n=0..6.

W. D. Smith, Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs

Yahoo Groups, Range Voting

Range Voting Yahoo Group, Introduction. [Cached copy]

RangeVoting.org, Group Website.

W. D. Smith, Survey on directed graph Ramsey Numbers.

Crossrefs

Cf. A122027, A003141.

Sequence in context: A164147 A321402 A210669 * A196721 A118034 A096590

Adjacent sequences: A122023 A122024 A122025 * A122027 A122028 A122029

Keyword

nonn

Author

Warren D. Smith, Sep 11 2006

Status

approved