A Linear Lower Bound for Dominating Sets in k-Majority Tournaments

2026/07/25 by Jiangdong Ai, Xiangjie Yi
#math.CO

paper · pdf

Abstract

A k-majority tournament on a finite vertex set is defined by 2k-1 linear orders, with u→ 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₁k/log k ≤ F(k) ≤ C₂klog k for suitable positive constants C₁ and C₂. In this paper, we prove the linear lower bound F(k)≥ \lfloor(k+1)/(2)\rfloor for k≥ 3.

Citations

• Approximately Dominating Sets in Elections
• A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
• Approval Gap of Weighted k-Majority Tournaments

Related

• Approval Gap of Weighted k-Majority Tournaments
• Acyclic Subgraphs in k-Majority Tournaments
• Dominant tournament families
• Domination in 3-tournaments
• Bounds on the Maximum Number of Minimum Dominating Sets