Tournaments not inducible by five voters
Abstract
How many members must a committee have before its pairwise majorities can express any collective preference? With enough voters every pattern of pairwise majorities, or tournament, can arise, but a committee of $k$ voters produces only some; for odd $k$, let $N(k)$ be the least number of alternatives on which some tournament arises from no $k$ voters. Only $N(3) = 8$ is known; for five voters our companion paper gave $12 \le N(5) \le 38$ and the first explicit example of moderate size, on 43 vertices. We show $13 \le N(5) \le 22$. The upper bound comes from nine tournaments on 22 vertices that five voters cannot produce: eight one-vertex deletions of doubly regular tournaments on 23 vertices, including every deletion of one of them, and one arc reversal. The Paley tournament on 23 vertices, which Bachmeier et al. (2019) left open after six weeks of SAT solving, is beyond five voters, and so is every other doubly regular tournament on 23 vertices. The lower bound comes from an analysis of all tournaments on 12 vertices. Both doubly regular tournaments on 19 vertices, the Paley tournament and one other, arise from five voters, but not with unit margin, that is, not with every majority carried by three votes to two. The method is a search that places one alternative at a time and exploits the tournament's symmetries; four of the negative results are certified by machine-checkable proofs, and all results are reproducible from a public repository.
- Comment
- 31 pages, 4 figures; v2: upper bound improved to $N(5) \leq 22$ (v1: $\leq 23$), refuting v1's conjecture $N(5) = 23$. Companion paper: arXiv:2607.26690