Fair splitting of colored paths

zbMATH Open1369.05157arXiv1704.02921MaRDI QIDQ2401427FDOQ2401427

Authors: Meysam Alishahi, Frédéric Meunier 

Publication date: 8 September 2017

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

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.

Full work available at URL: https://arxiv.org/abs/1704.02921

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

Recommendations

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

zbMATH Keywords

independent setsnecklace splittingoctahedral Tucker lemma

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

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

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)