The minimal covering set in large tournaments

Journal article

We prove that in almost all large tournaments, the minimal covering set is the entire set of alternatives. That is, as the number of alternatives gets large, the probability that the minimal covering set of a uniformly chosen random tournament is the entire set of alternatives goes to one. In contrast, it follows from a result of (Fisher and Reeves, Linear Algebra Appl 217:83-85, 1995) that the bipartisan set contains about half of the alternatives in almost all large tournaments. © 2010 Springer-Verlag.

Authors: Scott, A; Fey, M

• Publication status: Published
• Journal: SOCIAL CHOICE AND WELFARE
• Volume: 38
• Issue: 1
• Pages: 1-9
• Publication date: 2012-01-01
• DOI: 10.1007/s00355-010-0503-4
• EISSN: 1432-217X
• ISSN: 0176-1714
• Language: English