Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
Addressing the relationship between tournament structure and coloring, the authors present two alternative proofs bounding the domination number of a tournament by its fractional dichromatic number. While their first proof recovers the prior exponential VC-dimension bound via a reduction to $(1/2-\varepsilon)$-majority tournaments, their second proof drastically improves this relationship to a quasilinear bound. Notably, this near-optimal bound was discovered with AI assistance, drawing inspiration from recent structural proofs for Condorcet winning sets.
Tournament domination numbers don't scale exponentially with fractional dichromatic numbers after all: an AI-assisted proof slashes the known bound all the way down to quasilinear.
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].