This site is supported by donations to The OEIS Foundation.



Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A122026 Least number m such that every tournament with at least m nodes contains the acyclic n-node tournament. 1


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

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

%C 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.

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

%C 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.

%C 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.

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

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

%H W. D. Smith, <a href="http://rangevoting.org/PuzzDG.html">Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs</a>

%H Yahoo Groups, <a href="http://groups.yahoo.com/group/RangeVoting/">Range Voting</a>

%H W. D. Smith, <a href="http://rangevoting.org/PuzzRamsey.html">Survey on directed graph Ramsey Numbers</a>.

%Y Cf. A122027, A003141.

%K nonn

%O 0,3

%A _Warren D. Smith_, Sep 11 2006

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 18 14:15 EST 2014. Contains 252161 sequences.