Fractional Dichromatic Number and Domination in Tournaments
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.35186
curl -X POST /api/v1/records/arxiv/2609.35186/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.35186/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'