The set splittability problem

zbMATH Open1429.05015arXiv1611.01542MaRDI QIDQ5206923FDOQ5206923

Authors: Peter Bernstein, Cashous Bortner, Samuel Coskey, Shuni Li, Connor Simpson 

Publication date: 19 December 2019

Abstract: The set splittability problem is the following: given a finite collection of finite sets, does there exits a single set that contains exactly half the elements from each set in the collection? (If a set has odd size, we allow the floor or ceiling.) It is natural to study the set splittability problem in the context of combinatorial discrepancy theory and its applications, since a collection is splittable if and only if it has discrepancy $leq1$. We introduce a natural generalization of splittability problem called the $p$-splittability problem, where we replace the fraction $frac12$ in the definition with an arbitrary fraction $pin(0,1)$. We first show that the $p$-splittability problem is NP-complete. We then give several criteria for $p$-splittability, including a complete characterization of $p$-splittability for three or fewer sets ($p$ arbitrary), and for four or fewer sets ($p=frac12$). Finally we prove the asymptotic prevalence of splittability over unsplittability in an appropriate sense.

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

Recommendations

• On splitting and splittable families
• Even faster algorithm for set splitting!
• Tight hardness results for minimizing discrepancy
• Dividing splittable goods evenly and with limited fragmentation
• scientific article; zbMATH DE number 4168692

zbMATH Keywords

\(p\)-splittability problemhypergraph 2-colorability.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partitions of sets (05A18) Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) (05B10) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• Reducibility among combinatorial problems
• Six Standard Deviations Suffice
• Title not available (Why is that?)
• On generalizations of separating and splitting families
• Tight hardness results for minimizing discrepancy
• ``Integer-making theorems
• A stronger conclusion to the classical ham sandwich theorem
• A note on the Beck-Fiala theorem
• Constructive discrepancy minimization by walking on the edges
• On the Beck-Fiala theorem
• An improvement of the Beck-Fiala theorem

Cited In (3)

• Title not available (Why is that?)
• On splitting and splittable families
• On the splitting problem for selections

This page was built for publication: The set splittability problem

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