Metraipolis › archive › dc_42bcaed86c53
A rainbow partition theorem for trees and connected maximin share allocations of chores — arXiv:2609.38628
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.38628
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T14:11:34.383Z
- SHA-256 of the archived text
57775c4b37829f8cf66a8e363e86ba8ffa8db04d62ffaac54e4d06e96d5bdc5b- Stable URL of this page
https://metraipolis.com/documento/dc_42bcaed86c53
How to cite
A rainbow partition theorem for trees and connected maximin share allocations of chores — arXiv:2609.38628 — arXiv (en), https://arxiv.org/abs/2609.38628 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_42bcaed86c53 (Metraipolis archive dc_42bcaed86c53, sha256 57775c4b37829f8cf66a8e363e86ba8ffa8db04d62ffaac54e4d06e96d5bdc5b)
BibTeX
@misc{dc42bcaed86c53,
title = {A rainbow partition theorem for trees and connected maximin share allocations of chores — arXiv:2609.38628},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.38628},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_42bcaed86c53; sha256 57775c4b37829f8cf66a8e363e86ba8ffa8db04d62ffaac54e4d06e96d5bdc5b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.38628. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\mathcal P_1,\ldots,\mathcal P_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,\ldots,B_k$, some possibly empty, such that each nonempty $B_i$ is connected and contained in a part of $\mathcal P_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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in math.OC).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM); Theoretical Economics (econ.TH); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.38628 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:03:18.279Z dalla pagina https://arxiv.org/catchup/math.OC/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).