The minimal covering set in large tournaments
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 contra...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2012
|
| _version_ | 1797050593534017536 |
|---|---|
| author | Scott, A Fey, M |
| author_facet | Scott, A Fey, M |
| author_sort | Scott, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T18:07:27Z |
| format | Journal article |
| id | oxford-uuid:01ea4131-4a20-423f-9135-c46957c90789 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:07:27Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:01ea4131-4a20-423f-9135-c46957c907892022-03-26T08:37:32ZThe minimal covering set in large tournamentsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:01ea4131-4a20-423f-9135-c46957c90789EnglishSymplectic Elements at Oxford2012Scott, AFey, MWe 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. |
| spellingShingle | Scott, A Fey, M The minimal covering set in large tournaments |
| title | The minimal covering set in large tournaments |
| title_full | The minimal covering set in large tournaments |
| title_fullStr | The minimal covering set in large tournaments |
| title_full_unstemmed | The minimal covering set in large tournaments |
| title_short | The minimal covering set in large tournaments |
| title_sort | minimal covering set in large tournaments |
| work_keys_str_mv | AT scotta theminimalcoveringsetinlargetournaments AT feym theminimalcoveringsetinlargetournaments AT scotta minimalcoveringsetinlargetournaments AT feym minimalcoveringsetinlargetournaments |