Fractional dichromatic number bounds domination size in tournaments
Fractional Dichromatic Number and Domination in Tournaments
Discrete Mathematics
Summary
Tournaments are a special kind of network where every player beats another in a one-on-one game. A key question is how to find a small group of players that can influence or 'dominate' all others. The authors studied a mathematical measure called the fractional dichromatic number that helps estimate how big this dominating group must be. They provided two new proofs for a previous result, including one that uses artificial intelligence and offers a much tighter estimate. This work improves understanding of how tournament structure controls domination size.
What this means in practice
- •For network analysts: Use improved domination bounds to design smaller control sets in directed influence networks.
- •For election system designers: Incorporate tighter bounds on dominating sets to better understand coalition sizes needed in ranked voting scenarios.
A theory result. No direct application yet.
Authors
Paul Colinot, Alantha Newman
Abstract
Bourneuf, Charbit and Thomassé [BCT25] showed that the domination number of a tournament can be bounded as a function of its fractional dichromatic number. The function proved was exponential and the tools were based on VC-dimension. In this paper, we present two new proofs of this theorem. The first proof is based on a reduction to the problem of bounding the domination number of a $(1/2-ε)$-majority tournament, for which [BCT25] and Charikar, Ramakrishnan and Wang [CRW26] gave tight bounds. This proof yields the same exponential bound on the domination number as in [BCT25]. The second proof gives a quasilinear bound for the domination in terms of the fractional dichromatic number. It was obtained via AI and was inspired by the recent book proof of the existence of a Condorcet Winning Set of size five due to Ramakrishnan [Ram26].