Fair splitting of colored paths

MaRDI QIDQ2401427zbMATH OpenFDO

Authors Meysam Alishahi, Frédéric Meunier

Publication date 8 September 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.02921, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p41

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

independent setsnecklace splittingoctahedral Tucker lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: This paper deals with two problems about splitting fairly a path with colored vertices, where "fairly" means that each part contains almost the same amount of vertices in each color. Our first result states that it is possible to remove one vertex per color from a path with colored vertices so that the remaining vertices can be fairly split into two independent sets of the path. It implies in particular a conjecture of Ron Aharoni and coauthors. The proof uses the octahedral Tucker lemma. Our second result is the proof of a particular case of a conjecture of D{"o}m{"o}t{"o}r P{'a}lv{"o}lgyi about fair splittings of necklaces for which one can decide which thieves are advantaged. The proof is based on a rounding technique introduced by Noga Alon and coauthors to prove the discrete splitting necklace theorem from the continuous one.

Review text

Summary: This paper deals with two problems about splitting fairly a path with colored vertices, where ``fairly means that each part contains almost the same amount of vertices in each color.{ }Our first result states that it is possible to remove one vertex per color from a path with colored vertices so that the remaining vertices can be fairly split into two independent sets of the path. It implies in particular a conjecture of \textit{R. Aharoni} et al. [``Fair representation by independent sets, Preprint, \url{arXiv:1611.03196}]. The proof uses the octahedral Tucker lemma.{ }Our second result is the proof of a particular case of a conjecture of \textit{D. Pálvölgyi} [Electron. J. Comb. 16, No. 1, Research Paper R79, 8 p. (2009; Zbl 1186.05017)] about fair splittings of necklaces for which one can decide which thieves are advantaged. The proof is based on a rounding technique introduced by \textit{N. Alon} et al. [ACM Trans. Algorithms 2, No. 2, 153--177 (2006; Zbl 1321.68445)] to prove the discrete splitting necklace theorem from the continuous one.

Recommendations

• Splitting necklaces, with constraints
• Obstacles for splitting multidimensional necklaces
• Splitting necklaces
• Combinatorial necklace splitting
• scientific article; zbMATH DE number 496046

Cites work

• A combinatorical proof of Kneser's conjecture
• Algorithmic construction of sets for k -restrictions
• Combinatorial necklace splitting
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Fair representation by independent sets
• Generalized Kneser coloring theorems with combinatorial proofs
• Simplotopal maps and necklace splitting
• Splitting necklaces

Cited in

(8)

• The complexity of finding fair independent sets in cycles
• Fair splittings by independent sets in sparse graphs
• Fair representation in the intersection of two matroids
• The structural complexity landscape of finding balance-fair shortest paths
• Splitting loops and necklaces: variants of the square peg problem
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Constant inapproximability for PPA
• The complexity of finding fair independent sets in cycles

This page was built for publication: Fair splitting of colored paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401427)