A rainbow partition theorem for trees and connected maximin share allocations of chores
Abstract
Xiao, Qiu, and Huang (AAMAS 2023) and independently Lonc (personal communication) asked whether indivisible chores located at the vertices of a tree can always be allocated to n agents in connected bundles so that the cost of every agent is at most its connected maximin share; for goods, this is a theorem of Bouveret, Cechlárová, Elkind, Igarashi, and Peters. We answer the question affirmatively, even for monotone costs. The answer follows from a combinatorial theorem: if 𝒫1,…,𝒫k are partitions of the vertex set of a finite tree, each into at most k connected parts, then the vertex set can be split into disjoint sets B1,…,Bk, some possibly empty, such that each nonempty Bi is connected and contained in a part of 𝒫i. Equivalently, if each of k colours occurs on at most k−1 edges of a tree, then the vertices can be partitioned into connected sets labelled by distinct colours, none containing an edge of its own colour; in particular, one can choose for every colour a component of the forest obtained by deleting that colour so that the chosen components cover the tree. The bound is already best possible for paths, and for additive costs, the theorem is equivalent to the fair-division statement. The proof reduces the problem to inward partitions of oriented trees, which we obtain from the colourful KKM theorem on a simplex of edge weights, using a leaf-elimination labelling that remains compatible when weights vanish. We also give an algorithm running in time kO(k) plus polynomial time.
Related
- A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs
- A Bondy-type theorem for rainbow pancyclicity in graph systems
- A Lipschitz refinement of the Bebutov-Kakutani dynamical embedding theorem for connected Lie group actions
- Geometric lifting and Freiman's 3k−4 theorem in compact connected abelian groups
- Envy-Free Allocations for Random Non-Additive Valuations
BibTeX
@misc{anholcer2026rainbow,
title = {{A rainbow partition theorem for trees and connected maximin share allocations of chores}},
author = {Marcin Anholcer and Maciej Bartkowiak and Bartłomiej Bosek and Jarosław Grytczuk and Zbigniew Lonc and Paweł Rzążewski},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38628},
eprint = {2609.38628},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38628},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - A rainbow partition theorem for trees and connected maximin share allocations of chores
AU - Marcin Anholcer
AU - Maciej Bartkowiak
AU - Bartłomiej Bosek
AU - Jarosław Grytczuk
AU - Zbigniew Lonc
AU - Paweł Rzążewski
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.38628
UR - https://arxiv.org/abs/2609.38628
AB - Xiao, Qiu, and Huang (AAMAS 2023) and independently Lonc (personal communication) asked whether indivisible chores located at the vertices of a tree can always be allocated to n agents in connected bundles so that the cost of every agent is at most its connected maximin share; for goods, this is a theorem of Bouveret, Cechlárová, Elkind, Igarashi, and Peters. We answer the question affirmatively, even for monotone costs. The answer follows from a combinatorial theorem: if 𝒫_1,…,𝒫_k are partitions of the vertex set of a finite tree, each into at most k connected parts, then the vertex set can be split into disjoint sets B_1,…,B_k, some possibly empty, such that each nonempty B_i is connected and contained in a part of 𝒫_i. Equivalently, if each of k colours occurs on at most k−1 edges of a tree, then the vertices can be partitioned into connected sets labelled by distinct colours, none containing an edge of its own colour; in particular, one can choose for every colour a component of the forest obtained by deleting that colour so that the chosen components cover the tree. The bound is already best possible for paths, and for additive costs, the theorem is equivalent to the fair-division statement. The proof reduces the problem to inward partitions of oriented trees, which we obtain from the colourful KKM theorem on a simplex of edge weights, using a leaf-elimination labelling that remains compatible when weights vanish. We also give an algorithm running in time k^O(k) plus polynomial time.
ER -