

A122916


Minimum number of ncandidate fullrankorder ballots required to instantiate any tournament on n nodes (where A beats B in the tournament if and only if it does so in a majority of the ballots and we forbid pairwise ties).


0




OFFSET

1,2


COMMENTS

Every entry is an odd number. a(n) <= a(n+1) <= a(n)+4. For all large enough n we know Cn/log(n) < a(n) < Kn/log(n) for suitable constants 0<C<K. Additional entries should be within the reach of computers. a(19) >= 5.


LINKS

Richard Stearns, The voting problem, Amer. Math. Monthly 66 (1959) 761763. Warning: Erdos, Moser and Stearns actually consider a slightly different problem definition, where ties are allowed. That would define a different sequence which would upperbound this one and is related to it, but the present sequence seems to be a little more pleasant.


CROSSREFS



KEYWORD

hard,more,nonn


AUTHOR



STATUS

approved



