login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(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

%I

%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 October 1 06:15 EDT 2014. Contains 247503 sequences.