A122916 - OEIS

This site is supported by donations to The OEIS Foundation.

A122916

Minimum number of n-candidate full-rank-order 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).

1, 3, 3, 3, 3 (list; graph; refs; listen; history; internal format)

	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.`
	REFERENCES	`P. Erdos and L. Moser: On the representation of directed graphs as unions of orderings, Publ. Math. Inst. Hungar. Acad. Sci. 9 (1964) 125-132; also reprinted in Paul Erdos: The art of counting, Selected writings (ed. Joel Spencer) MIT Press 1973, pp. 79-86.` `Richard Stearns: The voting problem, Amer. Math. Monthly 66 (1959) 761-763. Warning: Erdos, Moser and Stearns actually consider a slightly different problem definition, where ties are allowed. That would define a different sequence which would upper-bound this one and is related to it, but the present sequence seems to be a little more pleasant.`
	LINKS	`Warren D. Smith, Answer to puzzle 28 (surveys the problem)`
	CROSSREFS	`Sequence in context: A031354 A200777 A033700 * A132973 A107760 A180560` `Adjacent sequences: A122913 A122914 A122915 * A122917 A122918 A122919`
	KEYWORD	`hard,more,nonn`
	AUTHOR	`Warren D. Smith (warren.wds(AT)gmail.com), Sep 19 2006`

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

Last modified February 17 21:13 EST 2012. Contains 206085 sequences.