← 研踪 PaperTrailarXiv:2609.35186 · v2
Elections, Fractional Dichromatic Number and Domination in Tournaments and Digraphs
首次提交 2026-09-28 21:49
版本更新 2026-11-16 23:07
雷达观测 2026-11-17 16:10
摘要
The dichromatic number of a digraph is the minimum number of induced acyclic sets into which its vertex set can be partitioned. The fractional dichromatic number is its fractional relaxation. Bourneuf, Charbit and Thomassé showed that the domination number of a tournament can be bounded as an (exponential) function of its fractional dichromatic number. This naturally leads to the question of finding a polynomial bound. We show that this bound is linear. To do this, we show a connection between undominated sets in elections and dominating sets in tournaments with bounded fractional dichromatic number. Within this framework, we also connect the well-known question of the existence of small Condorcet winning sets in elections to domination problems in digraphs with fractional dichromatic number less than 2. Thus, we open a new path to investigating these popular open problems in social choice from the perspective of graph theory.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-16 23:07 · 最新观测版本
Elections, Fractional Dichromatic Number and Domination in Tournaments and Digraphs
The dichromatic number of a digraph is the minimum number of induced acyclic sets into which its vertex set can be partitioned. The fractional dichromatic number is its fractional relaxation. Bourneuf, Charbit and Thomassé showed that the domination number of a tournament can be bounded as an (exponential) function of its fractional dichromatic number. This naturally leads to the question of finding a polynomial bound. We show that this bound is linear. To do this, we show a connection between undominated sets in elections and dominating sets in tournaments with bounded fractional dichromatic number. Within this framework, we also connect the well-known question of the existence of small Condorcet winning sets in elections to domination problems in digraphs with fractional dichromatic number less than 2. Thus, we open a new path to investigating these popular open problems in social choice from the perspective of graph theory.
查看此版本解读 →查看此版本原文 ↗