The set splittability problem

MaRDI QIDQ5206923zbMATH OpenFDO

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

Publication date 19 December 2019

Full work available at URL https://arxiv.org/abs/1611.01542, http://ajc.maths.uq.edu.au/pdf/75/ajc_v75_p190.pdf

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)

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.

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

Cites work

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

Cited in

(3)

• scientific article; zbMATH DE number 1193306 (Why is no real title available?)
• 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)