{"id":"arxiv/2607.23148","url":"https://arxiv.org/abs/2607.23148","tags":["math.CO"],"score":0,"title":"A Linear Lower Bound for Dominating Sets in $k$-Majority Tournaments","domain":"math.CO","source":"arxiv","authors":["Jiangdong Ai","Xiangjie Yi"],"reviews":0,"subject":"math.CO","summary":"A $k$-majority tournament on a finite vertex set is defined by $2k-1$ linear orders, with $u\\to v$ when $u$ lies above $v$ in at least $k$ of the orders. Let $F(k)$ be the maximum, over all $k$-majority tournaments, of the size of a minimum dominating set. Alon, Brightwell, Kierstead, Kostochka, and Winkler proved that $C_1k/\\log k \\leq F(k) \\leq C_2k\\log k$ for suitable positive constants $C_1$ and $C_2$. In this paper, we prove the linear lower bound $F(k)\\ge \\left\\lfloor\\frac{k+1}{2}\\right\\rfloor $ for $k\\ge 3$.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-25","reactions":{}}