Paperlane

no. 12 · Tuesday 10 November 2026

The maximum domination number of $k$-majority tournaments

Jiangdong Ai and Xiangjie Yi

math.CO · v2 · 10 pp

Abstract

A tournament is a \emph{$k$-majority tournament} if it is the pairwise majority relation of an election with $2k-1$ voters: there are $2k-1$ linear orders of the vertex set, repetitions allowed, such that $u\to v$ exactly when $u$ precedes $v$ in at least $k$ of them. Let $F(k)$ be the maximum domination number of a $k$-majority tournament. In 2006, Alon, Brightwell, Kierstead, Kostochka and Winkler proved that $F(k)$ is finite and that $c_1k/\log k\le F(k)\le c_2k\log k$ for absolute constants $c_1,c_2>0$; the order of growth of $F(k)$ has been open since. We prove that $F(k)=Θ(k\log k)$. As a consequence, the maximum domination number of a tournament realized by fair $m$-sided dice is $Θ(m\log m)$, closing the corresponding gap in the bounds of Alon et al.

comments
10 pages
fields
Combinatorics
pdf ↗ page arXiv:2607.23148 ↗